Leetcode–Sum Root to Leaf Numbers

The Problem:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Notes:

  1. This is a basic tree traversal problem. The key is to only add to final output at leaf nodes.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int sum = 0;
    public int sumNumbers(TreeNode root) {
        if(root==null)
            return 0;
        sumPath(root, 0);
        return sum;
    }
    
    public void sumPath(TreeNode root, int pass){
        if(root.left==null && root.right==null){
            // leaf node, add to final result
            sum+= 10 * pass + root.val;
        }
        else {
            if(root.left!= null){
                 sumPath(root.left, 10 * pass + root.val);
            }
             if(root.right!= null){
                 sumPath(root.right, 10 * pass + root.val);
            }
        }
    }
}

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);
    }
}

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–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;
    }
}

Leetcode–Minimum Depth of Binary Tree

The Problem:

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Notes:

  1. Basic question, similar to Maximum Depth of Binary Tree.

Java Solution


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root== null) return 0;
        return getMin(root, 1);
    }
    private int getMin(TreeNode root, int depth){
        if(root.left== null &&  root.right==null)
            return depth;
        int left=Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        if(root.left!= null)
            left = getMin(root.left, depth+1);
        if(root.right!= null)
            right = getMin(root.right, depth+1);
        
        return Math.min(left , right);
    }
}

Java Solution II

Actually it can be simpler than the above solution, since it does not pass in and out the depth, only one way will do. Be careful about cases that have left/right subtree empty.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root== null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if(left==0 && right== 0) return 1;
        else if(left==0 || right ==0) return Math.max(left, right)+1;
        else return Math.min(left, right)+1;
    }
    
}

Leetcode–Maximum Depth of Binary Tree

The Problem:

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

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 int maxDepth(TreeNode root) {
        if(root== null) return 0;
        return getMax(root, 1);
    }
    private int getMax(TreeNode root, int depth){
        if(root.left== null && root.right==null)
            return depth;
        int left=depth;
        int right = depth;
        if(root.left!= null)
            left = getMax(root.left, depth+1);
        if(root.right!= null)
            right = getMax(root.right, depth+1);
        
        return Math.max(left , right);
    }
}

A simpler one.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root== null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right)+1;
    }
    
}