Leetcode–Validate Binary Search Tree

The Problem:

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

Assume a 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.

Notes:

  1. Note that a valid BST should have ALL node in the left less than the root (of each level), not only the immediate left child. This impose a min-max constraint of all the nodes other than top root.
  2. In the recursion, it also pass that min-max constraint from top to bottom. In each recursion it checks left and right node not only valid for their parent (left < root < right), but also check if they are in the min-max range (The range is built up by all their ancestors).

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   public boolean isValidBST(TreeNode root){
        return isValid(root Integer.MIN_VALUE, Integer.MAX_VALUE) ;
    }
 
    private boolean isValid(TreeNode root, int min, int max){
        if(root==null) return true;
        if(root.val <= min || root.val >= max)
            return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }
}
Advertisements

Leetcode–Triangle

The Problem:

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Notes:

  1. The main idea is traversing the list backwards, which means start from bottom of the triangle. For each level up, store the result of min path to reach this node from lower level.
  2. It is a DP problem, but the previous results for one level can be updated in place.

Java Solution

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1)
            return triangle.get(0).get(0);
        int rows = triangle.size();
        int sum[] = new int[triangle.get(rows-1).size()];
        for(int i = 0; i < triangle.get(rows-1).size(); i++ ){
            sum[i] = triangle.get(rows-1).get(i);
        }
        
        for(int i = rows-2; i>= 0; i--){
            for(int j = 0; j <  triangle.get(i).size(); j++ ){
                sum[j] = triangle.get(i).get(j) + Math.min(sum[j], sum[j +1]);
            }
        }
        return sum[0];
    }
}

Leetcode–Flatten Binary Tree to Linked List

The Problem:

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Notes:

  1. Use a stack to record node.right if need to move node.left there.
  2. Mistake I made : remember to reset the node.left to null if moved.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return ;
        Stack<TreeNode> st = new Stack<TreeNode>();
        st.push(root);
        TreeNode fkHead = new TreeNode(0);
        TreeNode pre = fkHead;
        while(!st.empty()){
            TreeNode p = st.pop();
            pre.right = p;
            pre = p;
            while(p.right!= null || p.left != null){
                if(p.right!= null && p.left != null){
                    //--!!--only push to stack if both not null
                    st.push(p.right);
                    p.right = p.left;
                    //--!!!---remember to remove the left from tree
                    p.left = null;
                }
                else if(p.left != null){
                    p.right = p.left;
                    //--!!!---remember to remove the left from tree
                    p.left = null;
                }
                p = p.right;
                pre = p;
            }
        }
    }
}

Leetcode–Unique Binary Search Trees II

The Problem:

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Notes:

  1. Same observation as Unique Binary Search Trees : for each i being the root, it has left subtrees of the number as i-1 nodes unique BST , its has unique right subtree of the number as n-i nodes unique BST.
  2. For each root node i, construct a list of its left subtrees with nodes of [start, i-1], and a list of its right subtrees with nodes of [i+1, end]; then get all the possible left right subtree combo, and add to result.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; left = null; right = null; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return constructTree(1, n);
    }
    
    private List<TreeNode> constructTree(int start, int end ){
        List<TreeNode> result= new ArrayList<TreeNode>();
        if(start > end){
            result.add(null);
            return result;
        }
        if(start == end){
            result.add(new TreeNode(start));
            return result;
        }
            
        for(int i = start; i <= end; i++){
            List<TreeNode> leftNodes = constructTree(start, i-1);
            List<TreeNode> rightNodes = constructTree(i+1, end);
            for(int j = 0; j < Math.max(1,leftNodes.size()); j++){
                for(int k = 0; k < Math.max(1,rightNodes.size()); k++){
                    TreeNode root = new TreeNode(i);
                    if(leftNodes.size()!=0)
                        root.left = leftNodes.get(j);
                    if(rightNodes.size()!= 0)
                        root.right = rightNodes.get(k);
                    result.add(root);
                }
            }
        }
        return result;
    }
    
}

Leetcode–Unique Binary Search Trees

The Problem:

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Notes:

  1. Writing down a few examples, we can observe a fact: for each i being the root, it has left subtrees of the number as i-1 nodes unique BST , its has unique right subtree of the number as n-i nodes unique BST. So we can use DP to solve the problem iteratively.

Java Solution

public class Solution {
    public int numTrees(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        int[] count = new int[n+1];
        count[0] = 1;
        count[1] = 1;
        count[2] = 2;
        int k = 0;
        for(int j = 3; j <= n; j++){
            for(int i = 1; i <=j; i++){
                //take i as the root
                count[j] += count[i-1] * count[j-i];
            }
        }
        return count[n];
    }
}

Leetcode–Symmetric Tree

The Problem:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Bonus points if you could solve it both recursively and iteratively.

Notes:

  1. The recursive method is straightforward use DFS, we can raverse the left and right sub tree, and check if return the same result, can use in-order/pre-order/post-order/level-order, here notice that the empty nodes should also be recorded because otherwise sub trees may not have same traversal result but with different structure. See solution I
  2. Another recursive solution is directly compare left.left with right.right, while traversing, see solution II.
  3. The iterative method can be easily achieved use BFS, check for each level if the nodes are symmetric, see solution III.

Java Solution I recursive

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        List<Integer> subL = new ArrayList<Integer>();
        List<Integer> subR = new ArrayList<Integer>();
        subL = traverse(root.left, subL, 0);
        subR = traverse(root.right, subR, 1);
        return(subL.toString().equals(subR.toString()))            
    }
    
    private List<Integer> traverse(TreeNode root, List<Integer> list, int type){
        if(root==null){
            list.add(Integer.MIN_VALUE);
            return list;
        }
        list.add(root.val);
        if(type==0){
            list = traverse(root.left, list, 0);
            list = traverse(root.right, list, 0);
        }
        else{
           list = traverse(root.right, list , 1); 
           list = traverse(root.left, list, 1);
        }
        return list;
    }
}

Java Solution II recursive

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return compare(root.left, root.right, true);
    }
    
    private Boolean compare(TreeNode lt, TreeNode rt, Boolean lastres){
        if(!lastres){
            return false;
        }        
        //one end early
        if((rt == null && lt!=null) || (rt !=null && lt ==null)){
            return false;
        }   
        //if not leaf
        else if(rt !=null && lt != null){
            if(rt.val != lt.val){
                return false;
            }else{
                Boolean outcomp= compare(lt.left, rt.right, true); //match the nodes in mirror
                Boolean incomp = compare(lt.right, rt.left, true);
                return (outcomp&incomp);
            }
        }
        else{//the parent is leaf node
            return true;
        }
    }
}

Java Solution III iterative

It’s wrong but I don’t know why. Any idea?

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        Queue<TreeNode> nxtLv = new LinkedList<TreeNode>();
        int lvCount = 0;
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node.left==null)
                nxtLv.add(new TreeNode(Integer.MAX_VALUE));
            else{
                lvCount++;
                nxtLv.add(node.left);
            }
            if(node.right==null)
                nxtLv.add(new TreeNode(Integer.MAX_VALUE));
            else {
                nxtLv.add(node.right);
                lvCount++;
            }
            //this level finished
            if(q.isEmpty()){
                if(lvCount==0)
                    break;
                lvCount=0;
                if(!checkSymmetric(nxtLv))
                    return false;
                q=nxtLv;
                nxtLv = new LinkedList<TreeNode>();
            }
        }
        return true;   
    }
    
    private boolean checkSymmetric(Queue<TreeNode> q){
        ArrayList<Integer> arr = new ArrayList<Integer>();
        while(!q.isEmpty()){
            TreeNode t = q.poll();
            arr.add(t.val);
        }
        int i = 0;
        int j = arr.size()-1;
        while(i<j){
            if(arr.get(i)!= arr.get(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

Leetcode–Same Tree

The Problem:

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Notes:

  1. Basic question.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q== null)
            return true;
        else if(p!= null && q!= null &&
            p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right))
            return true;
        else 
            return false;
    }
}