代码随想录算法训练营第二十三天

LeetCode 669. 修剪二叉搜索树

依照指定的范围 [low, high] 修剪一颗二叉搜索树，删除所有在范围以外的节点

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        
        if (root == null) {
            return null;
        }
				
				// as this is a BST, if root's val is larger than high 
				// then all the right side nodes should be removed
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
				
				// the same with the left side
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
				
				// else, it means that root is within the target range
				// thus trim its child nodes
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;

    }
}

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

思路并不复杂，有序数组构建二叉搜索树，首先找到中间节点, 然后用左侧部分构建左树， 右侧构建右树，注意在递归的过程中维持循环不变量——左闭右开区间。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // as I do not wanna change the array itself thus I choose to use to helper
        // function and express the range 
        return buildBST(nums, 0, nums.length);
    }


    // build the tree and return the root node in range [startIndex, endIndex)
    private TreeNode buildBST (int[] nums, int startIndex, int endIndex){
        
        if (startIndex >= endIndex) {
            return null;
        }

        // pre-order
        int mid = (endIndex - startIndex) / 2 + startIndex;
        TreeNode root = new TreeNode (nums[mid]);
        
      	// maitain the invirants- the range [startIndex, endIndex)
        root.left = buildBST(nums, startIndex, mid);
        root.right = buildBST(nums, mid + 1, endIndex);
        return root;

    }
}

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

一开始没注意从rightmost节点开始遍历可以一次遍历完成所有操作

class Solution {
    private int temp = Integer.MIN_VALUE;

    public TreeNode convertBST(TreeNode root) {

        myConvertTree(root);
        return root;
    }


    private void myConvertTree (TreeNode root) {
        
        if (root == null) {
            return;
        }

        // reflect the target tree, we can find that it starts counting 
        // with the right node, then root node
        // and then the left node, thus we can traverse the tree in a variant in-order
        // i.e. right mid left 
        myConvertTree(root.right);

        // use a temp variable to record the updated value of the prev node thus we can 
        // change all the nodes in one traverse
        if (temp != Integer.MIN_VALUE) {
            root.val += temp;
        }

        temp = root.val;

        myConvertTree(root.left);
    }

}