二叉树

56. 合并区间 链接：56. 合并区间 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 区间判重，更新 end； 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end()); // 核心，先排序 int start = intervals[0][0]; int end = intervals[0][1]; vector<vector<int>> res; for (int i = 1; i < (int)intervals.size(); i++) { int left = intervals[i][0]; int right = intervals[i][1]; if (left <= end) { if (right > end) { end = right; } else { continue; } } else { res.push_back({start, end}); start = left; end = right; } } // 最后一组元素需要手动push res.push_back({start, end}); return res; } }; 738. 单调递增的数字 链接：738. 单调递增的数字 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 第一想法是拿个 vector 把数字都装起来，但是之后怎么做不明白； ...

669. 修剪二叉搜索树 链接：669. 修剪二叉搜索树 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 在小于low的节点，节点和左树全部抛掉，返回右树（如果右树不存在一样返回）； 大于high的节点，节点和右树全部抛掉，返回左树（如果左树不存在一样返回）； 看完题解后的想法 要学会运用返回节点简化操作，这题和LC450类似，都是用返回节点简化了左右判断，因为BST自带左右； 实现中遇到的困难 – 代码 class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if (!root) return nullptr; if (root->val < low) { return trimBST(root->right, low, high); } if (root->val > high) { return trimBST(root->left, low, high); } root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; } }; 108. 将有序数组转换为二叉搜索树 链接：108. 将有序数组转换为二叉搜索树 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 不断取中点构造二叉树; ...

235. 二叉搜索树的最近公共祖先 链接：235. 二叉搜索树的最近公共祖先 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 利用二叉搜索树的性质，可以用数值大小确定子树，第一次遇到的在 [p, q] 或者 [q, p] 间的数，就是最近公共祖先； BST 中，对于当前节点 cur，有三种情况： 情况一：cur 的值比 p 和 q 都大。说明 p 和 q 都在 cur 的左子树里，公共祖先一定在左边，cur 不是答案。 情况二：cur 的值比 p 和 q 都小。同理，都在右子树，往右走。 情况三：cur 的值在 p 和 q 之间（含等于）。这时候只有两种可能： p 和 q 分别在 cur 的左右子树 → cur 就是公共祖先 cur 本身就是 p 或 q 中的一个，另一个在它的子树里 → cur 也是公共祖先 看完题解后的想法 – 实现中遇到的困难 需要确定 p 和 q 的大小关系； 代码 class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (p->val > q->val) swap(p, q); TreeNode* cur = root; while (cur) { if (cur->val >= p->val && cur->val <= q->val) { return cur; } else if (cur->val < p->val) { cur = cur->right; } else { cur = cur->left; } } return nullptr; } }; 701. 二叉搜索树中的插入操作 链接：701. 二叉搜索树中的插入操作 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 二叉搜索树，可以直接比大小前进；然后找到空位就可以插进去了； ...

530. 二叉搜索树的最小绝对差 链接：530. 二叉搜索树的最小绝对差 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 中序遍历是有序的，直接用当前减过去； 看完题解后的想法 – 实现中遇到的困难 需要对最左节点进行一个特判，因为最左节点没有可以相减的； 代码 class Solution { public: int res = INT_MAX; int prev = -1; // -1 表示还没访问过任何节点 void dfs(TreeNode* root) { if (!root) return; dfs(root->left); if (prev != -1) { res = min(res, root->val - prev); // BST中序是升序，不需要abs } prev = root->val; dfs(root->right); } int getMinimumDifference(TreeNode* root) { dfs(root); return res; } }; 501. 二叉搜索树中的众数 链接：501. 二叉搜索树中的众数 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 遍历+哈希，直接在递归中怎么做不知道； ...

654. 最大二叉树 链接：654. 最大二叉树 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 和LC105, 106一样, 但是逻辑更加简单,直接采用传index; 看完题解后的想法 – 实现中遇到的困难 注意index是全局index所以直接传 代码 class Solution { public: TreeNode* recurse(vector<int>& nums, int begin, int end) { if (begin == end) return nullptr; // 1. 找到max值和index，这就是root int indexRoot = begin; for (int i = begin; i < end; i++) { if (nums[i] > nums[indexRoot]) { indexRoot = i; } } TreeNode* root = new TreeNode(nums[indexRoot]); // 2. 挂树+直接传index做分组，注意index是全局index所以直接传 root->left = recurse(nums, begin, indexRoot); root->right = recurse(nums, indexRoot+1, end); return root; } TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return recurse(nums, 0, (int)nums.size()); } }; 617. 合并二叉树 链接：617. 合并二叉树 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 使用递归， 返回 root1 ， 只要 root1 没有某棵树， 就挂上 root2 的； ...

513. 找树左下角的值 链接：513. 找树左下角的值 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 层序遍历，每层的第一个值 看完题解后的想法 实现中遇到的困难 代码 class Solution { public: int findBottomLeftValue(TreeNode* root) { int res; if (!root) { return res; } queue<TreeNode*> q; q.push(root); while (!q.empty()) { int num = q.size(); for (int i = 0; i < num; i++) { TreeNode* cur = q.front(); q.pop(); if (i == 0) { res = cur->val; } if (cur->left) { q.push(cur->left); } if (cur->right) { q.push(cur->right); } } } return res; } }; 112. 路径总和 链接：112. 路径总和 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 DFS+回溯；栈自带回溯； ...

110. 平衡二叉树 链接：110. 平衡二叉树 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 没想出来; 看完题解后的想法 从底到顶递归算高度,很巧妙; 对于底层叶子往上递归的过程需要理解; 实现中遇到的困难 代码 class Solution { public: bool isBalanced(TreeNode* root) { return getHigh(root) != -1; } int getHigh(TreeNode* root) { // 1. 递归到底之后返回 0 if (!root) { return 0; } // 2. 左子树高度 int left = getHigh(root->left); if (left == -1) return -1; // 3. 右子树高度 int right = getHigh(root->right); if (right == -1) return -1; if (abs(left - right) > 1) { return -1; } // 4. 返回当前高度,注意因为叶子节点的左右子树都是 nullptr 返回了 0,高度为 1 return 1 + max(left, right); } }; 257. 二叉树的所有路径 链接：257. 二叉树的所有路径 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 使用递归，一层加一个路径； ...

226. 翻转二叉树 链接：226. 翻转二叉树 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 遍历节点，然后交换节点的左右子树，DFS和BFS都能做； 看完题解后的想法 注意中序遍历因为是 左-根-右 ，在根节点交换完之后要继续访问左子树，因为已经交换了； 实现中遇到的困难 中序和后序的迭代写法还是记不牢； 代码 前序递归解： class Solution { public: TreeNode* invertTree(TreeNode* root) { dfs(root); return root; } void dfs(TreeNode* root) { if (!root) return; TreeNode* tmp = root->right; root->right = root->left; root->left = tmp; dfs(root->left); dfs(root->right); } }; 中序递归解： class Solution { public: TreeNode* invertTree(TreeNode* root) { dfs(root); return root; } void dfs(TreeNode* root) { if (!root) return; dfs(root->left); TreeNode* tmp = root->right; root->right = root->left; root->left = tmp; dfs(root->left); // 交换左右所以记得继续走左 } }; 前序迭代： ...

递归和栈都需要 O(h) 额外空间。Morris 遍历通过临时修改树结构，用 O(1) 空间完成前中后序遍历。每一步都画图讲清楚。

需要了解二叉树的种类，存储方式，遍历方式以及二叉树的定义。 文章：代码随想录 - 二叉树理论基础 DFS 144. 二叉树的前序遍历 链接：144. 二叉树的前序遍历 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 根 - 左 - 右 可以递归dfs，还可以迭代用栈模拟，还可以用Morris，但是Morris太复杂了； 看完题解后的想法 前序是"根-左-右"，弹出就访问，访问完把左右子节点压栈。节点被弹出只有一种含义：该访问了。不存在"我还要回来"的情况。 实现中遇到的困难 注意压栈的顺序是后访问的先压; 代码 递归解：(爆栈风险) class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; dfs(root, res); return res; } void dfs(TreeNode* root, vector<int>& res) { if (root == nullptr) { return ; } res.push_back(root->val); dfs(root->left, res); dfs(root->right, res); } }; 迭代解：(面试要求) class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; if (!root) { return res; } stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); res.push_back(cur->val); // 先压后访问的 if (cur->right) { st.push(cur->right); } // 再压先访问的 if (cur->left) { st.push(cur->left); } } return res; } }; 145. 二叉树的后序遍历 链接：145. 二叉树的后序遍历 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 左 - 右 - 根, 迭代解不会; ...