代码随想录算法训练营第二十三天 | 修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转换为累加树

669. 修剪二叉搜索树

leetcode
文档题解
视频题解

二叉搜索树，有序性，不满足条件的区间就可以被排除。

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;

        if (root.val < low) {
            // 当前节点小于下界，则其左子树直接排除，去遍历右子树
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            // 当前节点大于上界，则其右子树直接排除，去遍历左子树
            return trimBST(root.left, low, high);
        }

        // root 在区间内，保持不变，遍历左右子树
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        return root;
    }
}

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

leetcode
文档题解
视频题解

构造二叉树的关键在于提供的序列是什么序列，以及构成什么样的二叉树。序列有前序、中序、后序、层序，二叉树有普通二叉树和二叉搜索树等。

本题要构造二叉搜索树，且给出的序列是有序序列，那么直接分区就行，一般都是从序列的中间开始划分左右区域，否则构造的二叉树不平衡，容易斜。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums, 0, nums.length - 1);
    }

    public TreeNode traversal(int[] nums, int l, int r) {
        if (l > r) return null;
        // 优化，如果 l、r 相等，则直接生成节点并返回，不用再往下递归了
        if (l == r) return new TreeNode(nums[l]);
        // 每次取中间
        int mid = (l + r) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = traversal(nums, l, mid - 1);
        node.right = traversal(nums, mid + 1, r);
        return node;
    }
}

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

leetcode
文档题解
视频题解

根据二叉搜索树有序的性质，按后、中、左的顺序遍历，运用了双指针的技巧。

class Solution {
    private TreeNode prev;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;

        root.right = convertBST(root.right);

        // prev 是右面的值，比中、左都大
        // 所以直接累加即可
        if (prev != null) {
            root.val += prev.val;
        }
        prev = root;

        root.left = convertBST(root.left);

        return root;
    }
}

递归也可以不返回节点，只处理累加值即可。

class Solution {
    private int prevVal;
    public TreeNode convertBST(TreeNode root) {
        traversal(root);
        return root;
    }
    public void traversal(TreeNode root) {
        if (root == null) return;

        traversal(root.right);

        root.val += prevVal;
        prevVal = root.val;

        traversal(root.left);
    }
}