代码随想录算法训练营第23天

今日任务

● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

链接：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C (opens in a new tab)

669. 修剪二叉搜索树

题解想法

如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。

如果root（当前节点）的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。

将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。最后返回root节点。

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

回顾

思考：节点是如何从二叉树中移除的

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

自己想法

二分

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return invert(nums, 0, nums.length);
    }
    // [start, end)
    public TreeNode invert(int[] nums, int start, int end) {
        if(start == end) return null;
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = invert(nums, start, mid);
        root.right = invert(nums, mid + 1, end);
        return root;
    }
}

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

自己想法

右中左遍历，遍历的时候新建中间节点，并接住左右的返回值。用全局变量记录当前的累加和。

class Solution {
    public int now_sum = 0;
    public TreeNode convertBST(TreeNode root) {
        return invert(root);
    }
    // 右中左
    public TreeNode invert(TreeNode root) {
        if(root == null) return null;
        TreeNode sum_root = new TreeNode();
        sum_root.right = invert(root.right);
        sum_root.val = root.val + this.now_sum;
        this.now_sum = sum_root.val;
        sum_root.left = invert(root.left);
        return sum_root;
    }
}