669.修剪二叉搜索树

题目链接：669.修剪二叉搜索树
文档讲解：代码随想录
状态：据说很难，但是轻松AC

思路

注意二叉搜索树的性质，当某一节点很小时，他的左子树要删掉，右子树待定；反之同理。

题解

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr)return root;
        if(root->val<low)return trimBST(root->right, low, high);
        else if(root->val>high)return trimBST(root->left, low, high);
        else
        {
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
            return root;
        }
    }
};

108.将有序数组转换为二叉搜索树

题目链接：108.将有序数组转换为二叉搜索树
文档讲解：代码随想录
状态：轻松AC

思路

本题考虑到平衡二叉树，其定义为：该树所有节点的左右子树高度相差不超过1

平衡二叉树每一个子树都要满足高度要求，所以其外观有一点点像完全二叉树，这里一开始有误区！！！

平衡二叉搜索树一定和中序遍历、二分查找联系起来，所以问题转变为了找中间节点（左右相差最多1个，不影响平衡性），然后是常规的递归建树问题。

题解

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.empty())return nullptr;
        int mid = nums.size()/2;
        TreeNode* root = new TreeNode(nums[mid]);
        vector<int> left(nums.begin(),nums.begin()+mid);
        vector<int> right(nums.begin()+mid+1,nums.end());
        root->left = sortedArrayToBST(left);
        root->right = sortedArrayToBST(right);
        return root;
    }
};

538.把二叉搜索树转换为累加树

题目链接：538.把二叉搜索树转换为累加树
文档讲解：代码随想录
状态：理清递归顺序与要求，轻松AC

思路

本题要求使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和，所以遍历顺序从大到小->故推出递归顺序为右中左。

在右中左遍历过程中，当前节点的值等于当前节点加上上一个节点，要和父节点连接起来，妥妥的pre节点没毛病！

题解

class Solution {
public:
    TreeNode* pre = nullptr;
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr)return nullptr;
        //右中左
        root->right = convertBST(root->right);
        if(pre!=nullptr)root->val = root->val+pre->val;
        pre = root;
        root->left = convertBST(root->left);
        return root;
  
    }
};

二叉树总结

👏👏👏超长的二叉树章节终于结束了！👏👏👏

来总结一下吧 ······

二叉树的种类

得先知道二叉树是啥子吧，对于算法题目来说，几乎所有的树都是链式法则，也就是一个节点有左右两个指针。所以，想玩转二叉树，先熟悉链表的操作吧！

二叉树里面有个特殊的：搜索树，他的性质异常重要，因为其有序性，所以在搜索时有方向性。处理该树用的最多的是中序遍历+pre指针。

当严格按照二分法时，搜索树就变成了较为漂亮的平衡搜索树，也要了解其构建过程哦！

二叉树的遍历方式

👀二叉树就是根节点+左子树+右子树，右子树呢？等于根节点+左子树+右子树······子子孙孙无穷尽矣（好像不对，到了空节点就穷尽了），这引出了递归法，也是最关键最重要的思想！

二叉树的递归遍历分为前序、中序、后续遍历，都是深度优先搜素；关键在于处理节点的位置在哪里，灵活运用解题，要多理解。

还有一个是层序遍历，这个太熟啦，就是队列的应用，也很巧妙。

做题还得是递归，就是子树就是魔怔

题目类型

• 二叉树属性
  • 对称问题
  • 深度问题
  • 高度问题
  • 节点数量
  • 查找节点
  • 查找路径
  • 平衡性
  • 叶子节点问题
  • 公共祖先问题
• 二叉树修改与构造
  • 翻转问题
  • 构造问题
  • 合并问题
  • 插入问题
  • 删除问题
• 二叉搜索树
  • 搜索问题
  • 判断问题
  • 相邻大小比较

最后总结

• 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。

• 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。

• 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

所以求普通二叉树的属性还是要具体问题具体分析。

二叉树专题汇聚为一张图：

图片来源于 知识星球-青