二叉搜索树

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 的； ...