算法高頻題

刷題：LeetCode（Top 100-150題，至少刷兩遍）。重點：鏈表、樹、二分查找、動態規劃、回溯、棧/隊列。
每一個題型，前10個高頻題

算法思考框架參考：算法題思維框架-CSDN博客

高頻順序參考網站：CodeTop 面試題目總結

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);}
};