C++刷题笔记(27)——leetcode669、108、539

这一题的本质就是从二叉树中删除节点，比如示例二，就是要把节点0从二叉树中删除，那么就可以将节点0的右子树直接赋值给节点三的左子树

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return nullptr;
        if (root->val < low) root = trimBST(root->right, low, high);       //当前节点小于low，遍历右子树
        else if (root->val > high) root = trimBST(root->left, low, high);  //当前节点大于high，遍历左子树
        else {
            root->left = trimBST(root->left, low, high);                   //遍历左子树，并且更新root的左孩子
            root->right = trimBST(root->right, low, high);                 //遍历右子树，并且更新root的右孩子
        }
        return root;
    }
};

在代码中trimBST返回值是一个新子树的根节点，可以直接更新root，以此来完成从二叉树中移除节点的操作：



自己也可打上断点过一遍便于理解。

一个升序的数组和二叉搜索树，最应该想到的就是中序遍历；

那么这道题的意思就是用中序遍历恢复二叉搜索树，那么可以以升序数组中的任一个元素作为根节点，以该元素左边的升序数组构建左子树，以该元素右边的升序数组构建右子树

题目又要求高度平衡，那么可以选取升序数组的中间元素作为根节点，保证左右子树的元素相同。

还有一点要注意的是数组长度为偶数时，中间节点有两个，取哪一个都可以，构成的平衡二叉搜索树不一样。

class Solution {
public:
    TreeNode* traversal(vector& nums, int left, int right) {    //左闭右闭区间[left, right]
        if (left > right) return NULL;
        int mid = left + ((right - left) / 2);                       //计算中间点的位置，这里取了左边
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);                 //递归构建左子树
        root->right = traversal(nums, mid + 1, right);               //递归构建右子树
        return root;
    }
    TreeNode* sortedArrayToBST(vector& nums) {
        return traversal(nums, 0, nums.size() - 1);
    }
};

最后一句话的意思就是将每个节点的值 修改为 原来节点值加所有大于它的节点值之和。

比如根节点4，修改后4+5+6+7+8=30

如果通过中序遍历示例1的二叉搜索树，可以得到有序数组{0,1,2,3,4,5,6,7,8}，那么题目的要求就相当于有序数组从后往前累加，即{36,36,35,33,30,26,21,15,8}

只需要反中序遍历二叉搜索树，记录节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。

class Solution {
public:
    int pre = 0; // 记录前一个节点的数值
    void traversal(TreeNode* cur) { // 右中左遍历
        if (cur == NULL) return;
        traversal(cur->right);     
        cur->val += pre;            //让cur的数值加上前一个节点的数值
        pre = cur->val;
        traversal(cur->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        traversal(root);
        return root;
    }
};