DEV Community

Flame Chan
Flame Chan

Posted on

LeetCode Day18 Binary Tree Part 8

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced
binary search tree.

Example 1:

Image description
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Image description

Example 2:
Image description
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.

Original Page

Image description

    public TreeNode sortedArrayToBST(int[] nums) {

        if(nums.length == 0){
            return null;
        }

        if(nums.length == 1){
            return new TreeNode(nums[0]);
        }
        int size = nums.length;
        int mid = nums.length>>1;

        TreeNode root = new TreeNode(nums[mid]);

        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid+1, size));

        return root;
    }
Enter fullscreen mode Exit fullscreen mode

we only need to consider dividing the original array into two nearly the same size sub-arrays. Then link the part to the middle element and do it iteratively.

538. Convert BST to Greater Tree

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:
Image description
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Example 2:

Input: root = [0,null,1]
Output: [1,null,1]

Constraints:

The number of nodes in the tree is in the range [0, 104].
-104 <= Node.val <= 104
All the values in the tree are unique.
root is guaranteed to be a valid binary search tree.
Original Page

Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

According to the description the new node value will be added to the sum of the value that is larger than itself and this is a BST. Thus, it implies that we can process the logic from the rightest node (has biggest value) -> then middle -> then left.
A reverse version of an in-order transverse (right -> middle -> left)

    public TreeNode convertBST(TreeNode root) {
        if(root == null){
            return root;
        }

        greaterWork(root, 0);

        return root;

    }
    public int greaterWork(TreeNode cur, int cumulate){
        if(cur.left == null && cur.right == null){
            cur.val += cumulate;
            cumulate = cur.val;
            return cur.val;
        }

        if(cur.right!=null){
            cumulate = greaterWork(cur.right, cumulate);
        }


        cur.val += cumulate;
        cumulate = cur.val;

        if(cur.left != null){
            cumulate = greaterWork(cur.left, cumulate); 
        }

        return cumulate;
    }
Enter fullscreen mode Exit fullscreen mode

Method 2 we can refine this code by editing end logic use node == null instead of node == leaf node;

    public TreeNode convertBST(TreeNode root) {
        if(root == null){
            return root;
        }
        greaterWork(root, 0);

        return root; 
    }
    public int greaterWork(TreeNode cur, int cumulate){
        if(cur == null){
            return cumulate;
        }
        cumulate = greaterWork(cur.right, cumulate);

        cur.val += cumulate;
        cumulate = cur.val;

        cumulate = greaterWork(cur.left, cumulate); 

        return cumulate;
    }
}
Enter fullscreen mode Exit fullscreen mode

Method 3 we can use the method that build a global variable instead of a parameter of the new method

    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null){
            return root;
        }

        convertBST(root.right);

        root.val += sum;
        sum = root.val;

        convertBST(root.left);

        return root;

    }
Enter fullscreen mode Exit fullscreen mode

669. Trim a Binary Search Tree

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example 1:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]
Example 2:

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

Constraints:

The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 10^4
The value of each node in the tree is unique.
root is guaranteed to be a valid binary search tree.
0 <= low <= high <= 10^4

Wrong Code here

Debuging

class Solution {
    /**
    find low

    find high

    1. partent link
    2. child link
        a. low left child parent drop
        b, low right child parent fill in

        a. high left child fill in 
        b. high right child drop
     */
    //  TreeNode cur;
     TreeNode parent;
     TreeNode preParent;
     boolean isLeft;
    public TreeNode trimBST(TreeNode root, int low, int high) {
        TreeNode cur = root;
        parent = root;
        findTarget(cur, low);
        System.out.println(parent.val);
        System.out.println(cur.val);

        if(cur.val == root.val){
            root.left = null;
        }

        if(cur!=null){
            System.out.println("not null");
            if(cur.right == null){
                if(isLeft){
                    preParent.left = null;
                } else{
                    preParent.right = null;
                }
            } else{
                System.out.println("low right not null");
                if(isLeft){
                    preParent.left = cur.right;
                }else{
                    preParent.right = cur.right;
                }
            }
        }


        cur = root;
        parent = root;

        findTarget(cur, high);
        System.out.println(parent.val);
        System.out.println(cur.val);

        if(cur == root){
            cur.right = null;
        }
        if(cur!=null){
            if(cur.left == null){
                if(isLeft){
                    parent.left = null;
                } else{
                    parent.right = null;
                }
            } else{
                if(isLeft){
                    parent.left = cur.left;
                }else{
                    parent.right = cur.left;
                }
            }
        }

        return root;

    }
    public TreeNode findTarget(TreeNode cur, int target){

        if(cur == null){
            return null;
        }

        TreeNode result = findTarget(cur.left, target);
        if(result !=null){
            return result;
        }
        if(cur.val == target){
            return cur;
        }
        preParent = parent;
        parent = cur;

        return findTarget(cur.right, target);

    }
Enter fullscreen mode Exit fullscreen mode

Top comments (0)