1.树

1.1102. 二叉树的层序遍历 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-level-order-traversal/

思考：题目已经给出层序遍历，按照思考框架。

BFS:

 vector<vector<int>> levelOrder(TreeNode* root) {if(!root) return {};vector<vector<int>> ans;queue<TreeNode*> q;q.push(root);while(!q.empty()){int levelSize = q.size();vector<int> layer;for(int i = 0;i<levelSize;++i){auto node = q.front();q.pop();// process node->vallayer.push_back(node->val);if(node->left) q.push(node->left);if(node->right) q.push(node->right);}// current layer is overans.push_back(layer);}return ans;}

DFS:需要记录深度depth，回溯时根据depth添加到对应数组里。

class Solution {
public:vector<vector<int>> ans;void dfs(TreeNode* root,int depth){if(!root) return;if(depth>=ans.size()){ans.push_back({root->val});}else{ans[depth].push_back(root->val);}dfs(root->left,depth+1);dfs(root->right,depth+1);}vector<vector<int>> levelOrder(TreeNode* root) {if(!root) return {};dfs(root,0);return ans;}
};

1.2236. 二叉树的最近公共祖先 - 力扣（LeetCode）https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

思考：按照思维框架，我们可以看出先需要知道左右子树，显然是后续遍历。

具体思路：

如果当前节点为nullptr,返回nullptr。
如果当前节点就是p或q,那么返回当前节点。
递归遍历左子树和右子树，得到左右子树的结果。
如果左子树和右子树的结果都不为空，说明当前节点就是p和q的最近公共祖先。
如果左子树结果不为空，右子树结果为空，说明p和q都在左子树中，返回左子树的结果。
如果右子树结果不为空，左子树结果为空，说明p和q都在右子树中，返回右子树的结果。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr || root == p || root == q){return root;}TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(left!=nullptr && right!=nullptr){return root;}return left!=nullptr?left:right;}

时间复杂度：O(N),最坏情况下，我们需要访问所有节点。

空间复杂度：O(H),递归调用的栈深度取决于二叉树的高度，最坏情况下（树退化为链表）为 O(N)，平均情况下为 O(logN)。

1.3103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/

这道题BFS的变种，核心思路仍然仍按层遍历，但需要根据层数的奇偶性来决定遍历方向：

使用队列进行BFS：标准的层序遍历方法
使用标志位记录方向：用一个布尔值 leftToRight 记录当前层应该是从左到右还是从右到左
根据方向处理每层结果：
- 如果是左到右：直接按遍历顺序加入结果
- 如果是右到左：将当前层的结果反转后加入结果

方法一：标准BFS + 反转

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if(!root) return {};vector<vector<int>> res;queue<TreeNode*> q;q.push(root);bool leftToRight = true;while(!q.empty()){int levelSize = q.size();vector<int> layer(levelSize);for(int i = 0;i<levelSize;++i){auto node = q.front();q.pop();int index = leftToRight?i:levelSize-1-i;layer[index] = node->val;if(node->left) q.push(node->left);if(node->right) q.push(node->right);}res.push_back(layer);leftToRight = !leftToRight;}return res;}

时间复杂度：O(n)
空间复杂度：O(n)

方法二：使用双端队列（Deque）

这种方法更高效，避免了反转操作：

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> result;if (!root) return result;deque<TreeNode*> dq;dq.push_back(root);bool leftToRight = true;while (!dq.empty()) {int levelSize = dq.size();vector<int> currentLevel;for (int i = 0; i < levelSize; i++) {if (leftToRight) {// 从左到右：从前面取，往后面加（先左后右）TreeNode* node = dq.front();dq.pop_front();currentLevel.push_back(node->val);if (node->left) dq.push_back(node->left);if (node->right) dq.push_back(node->right);} else {// 从右到左：从后面取，往前面加（先右后左）TreeNode* node = dq.back();dq.pop_back();currentLevel.push_back(node->val);if (node->right) dq.push_front(node->right);if (node->left) dq.push_front(node->left);}}result.push_back(currentLevel);leftToRight = !leftToRight;}return result;}
};

方法三：DFS递归解法

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> result;dfs(root, 0, result);return result;}void dfs(TreeNode* node, int level, vector<vector<int>>& result) {if (!node) return;if (level >= result.size()) {result.push_back({});}if (level % 2 == 0) {// 偶数层：从左到右result[level].push_back(node->val);} else {// 奇数层：从右到左，插入到开头result[level].insert(result[level].begin(), node->val);}dfs(node->left, level + 1, result);dfs(node->right, level + 1, result);}
};

时间复杂度：O(N)，每个节点被访问一次
空间复杂度：O(N)，队列或递归栈的空间

1.4124. 二叉树中的最大路径和 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-maximum-path-sum/

思路：

采用后序遍历的递归方法：

递归函数定义：maxGain(TreeNode* node) 返回以该节点为起点的最大路径和（只能向下走）
计算当前节点的贡献值：
- 左子树的贡献：leftGain = max(maxGain(node->left), 0)
- 右子树的贡献：rightGain = max(maxGain(node->right), 0)
更新全局最大值：node->val + leftGain + rightGain
返回当前节点的最大贡献：node->val + max(leftGain, rightGain)

class Solution {
private:int maxSum = INT_MIN;public:int maxPathSum(TreeNode* root) {maxGain(root);return maxSum;}int maxGain(TreeNode* node) {if (!node) return 0;// 递归计算左右子树的最大贡献值，如果为负则取0（相当于不选择）int leftGain = max(maxGain(node->left), 0);int rightGain = max(maxGain(node->right), 0);// 当前节点作为转折点的路径和int priceNewPath = node->val + leftGain + rightGain;// 更新全局最大值maxSum = max(maxSum, priceNewPath);// 返回当前节点的最大贡献（只能选择一边）return node->val + max(leftGain, rightGain);}
};

时间复杂度：O(N)，每个节点访问一次
空间复杂度：O(H)，递归栈的深度，H为树的高度

1.5

199. 二叉树的右视图 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-right-side-view/思路：

这道题要求从右侧观察二叉树时能看到的节点，实际上就是求每一层最右边的节点。

主要有两种方法：

BFS层序遍历：记录每层的最后一个节点
DFS递归：按照根→右→左的顺序遍历，记录每层第一个访问到的节点

方法一：BFS层序遍历（推荐）

ector<int> rightSideView(TreeNode* root) {vector<int> result;if (!root) return result;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size();for (int i = 0; i < levelSize; i++) {TreeNode* node = q.front();q.pop();// 如果是当前层的最后一个节点，加入结果if (i == levelSize - 1) {result.push_back(node->val);}if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return result;}

方法二：DFS递归

思路：按照根→右→左的顺序遍历，每层第一个访问到的节点就是右视图能看到的节点。

class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> result;dfs(root, 0, result);return result;}void dfs(TreeNode* node, int depth, vector<int>& result) {if (!node) return;// 如果当前深度等于结果数组大小，说明是这一层第一个访问的节点（最右边）if (depth == result.size()) {result.push_back(node->val);}// 先递归右子树，再递归左子树dfs(node->right, depth + 1, result);dfs(node->left, depth + 1, result);}
};