刷题笔记Day21：二叉树part08

题目：修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣（LeetCode）

做错的原因：我在前序遍历二叉树的过程中只要碰到小于low的节点就直接返回右子树，在大于high的节点就直接返回左子树，这样做不能确保返回的左右子树是否满足要求，因此需要对返回的左右子树继续按照单层的判断逻辑进行判断

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

题目：将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

思路：每次找到序列的中心点，序列的左边即为左子树所对应的序列，右边为右子树所对应的序列

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

题目：把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

思路：采用的遍历方式是右中左就可以很好的解决这个问题

class Solution {
public:
    int sums = 0;
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr) return nullptr;
        
        root->right = convertBST(root->right);
        
        root->val += sums;
        sums = root->val;
​
        root->left = convertBST(root->left);
​
        return root;
    }
};