算法练习-day20

二叉树

669. 修剪二叉搜索树

题意：给你二叉搜索树的根节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在唯一的答案 。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意：根节点可能会根据给定的边界发生改变。

示例：

      思路：本题我们的思路是将满足判断区间的节点相连，即如上图所示，将0移除，然后拼接3和2这样的情况，因此，我们先遍历所有节点，然后找出需要拼接的节点，从下到上一层一层返回，将符合条件的节点拼接到一起，最终得到一颗符合条件的BST

C++代码：

    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(nullptr==root)
        {
            return root;
        }
        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. 将有序数组转换为二叉搜索树

题意：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例：

       思路：本题的思路就比较简单了，因为我们要创建的是BST，且数组已经是增序的了。因此，我们只需要将数组的中间节点找到，即可找到对应的根节点进行连接，然后将数组分为左右子树的数组重复上述操作，直到所有数组都没有元素，完成BST的创建

C++代码：

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0)//当数组为空时，代表节点连接完毕
        {
            return nullptr;
        }
        int mid=nums.size()/2;//找到中间节点，就是一棵BST的根节点
        TreeNode* root=new TreeNode(nums[mid]);
        vector<int> leftnums(nums.begin(),nums.begin()+mid);//分割出左右子树的元素
        vector<int> rightnums(nums.begin()+mid+1,nums.end());
        root->left=sortedArrayToBST(leftnums);//进行左右子树根节点的拼接
        root->right=sortedArrayToBST(rightnums);
        return root;
    }

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

题意：给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

1. 节点的左子树仅包含键 小于 节点键的节点。
2. 节点的右子树仅包含键 大于 节点键的节点。
3. 左右子树也必须是二叉搜索树。

示例：

思路：本题由于是BST的累加，因此，我们需要从最右侧开始累加，将最大的数最先累加，以此达到累加树的效果。

我们需要先找到最右侧节点，然后进行从下到上的累加，然后再从左子树从下到上累加，因此需要使用反转的中序遍历完成此操作。

C++代码：

    int cur=0;
    void CMT(TreeNode* root)//先遍历到树的最右侧，然后从下往上累加节点值，然后在遍历左侧节点从下往上累加
    {
        if(nullptr==root)
        {
            return;
        }
        CMT(root->right);
        root->val+=cur;//中间进行累加操作
        cur=root->val;
        CMT(root->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        CMT(root);
        return root;
    }