LeetCode Day 15 Binary Tree Part 5

LeetCode No. 617. Merge Two Binary Trees

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode root = new TreeNode();

        if(root1 == null && root2 == null){
            return null;
        }

        if(root1 == null){
            root = root2;
            root.left = mergeTrees(null, root2.left);
            root.right = mergeTrees(null, root2.right);
        }
        if(root2 == null){
            root = root1;
            root.left = mergeTrees(null, root1.left);
            root.right = mergeTrees(null, root1.right);
        }

        if(root1!=null && root2!=null){
            root.val = root1.val + root2.val;
            root.left = mergeTrees(root1.left, root2.left);
            root.right = mergeTrees(root1.right, root2.right);
        }

        return root;
    }

But I have written some trouble useless codes as well. I will truncate them.

Here we have let the root assign to non-null root reference

LeetCode 700. Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []
Constraints:

The number of nodes in the tree is in the range [1, 5000].
1 <= Node.val <= 107
root is a binary search tree.
1 <= val <= 107

    public TreeNode searchBST(TreeNode root, int val) {

        if(root == null || root.val == val){
            return root;
        }

        if(root.val < val){
            root = searchBST(root.right, val);
        } 
        else{
            root = searchBST(root.left,val);
        }
        return root;
    }

LeetCode 98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

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:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

Wrong Code

    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        return isBST(root.left,root.val, true, root.val, true) && 
            isBST(root.right, root.val, false, root.val,false);

    }

    public boolean isBST(TreeNode cur, int formerVal, boolean isLeft, int rootVal, boolean leftToRoot){
        if(cur == null){
            return true;
        }

        boolean isLeftToRoot = (leftToRoot && cur.val < rootVal) || 
                            (!leftToRoot && cur.val > rootVal);
        boolean isValidChild = (isLeft && cur.val < formerVal) ||
                            (!isLeft && cur.val > formerVal);

        if(isLeftToRoot && isValidChild){
            boolean leftTrue = isBST(cur.left, cur.val, true, rootVal,leftToRoot);
            boolean rightTure = isBST(cur.right, cur.val, false, rootVal,leftToRoot);
            return leftTrue && rightTure;
        } 
        return false;
    }

• 1, Add too many sub evaluation but cannot cover the full possibility
• 2, BST is a special data structure that each left child(left sub tree less than parent )
• ### so according to 2, we can get that instead of above pre-order traverse, we can use in-order traverse. left- mid - right it is increasing assignment.