Leetcode 102 Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution 1: recursive DFS

 public class Solution {  
   public List<List<Integer>> levelOrder(TreeNode root) {  
     List<List<Integer>> res=new ArrayList<>();  
     dfs(root,0,res);  
     return res;  
   }  
   private void dfs(TreeNode x, int d, List<List<Integer>> res) {  
     if (x==null) return;  
     if (d==res.size()) res.add(new ArrayList<Integer>());  
     res.get(d).add(x.val);  
     dfs(x.left,d+1,res);  
     dfs(x.right,d+1,res);  
   }  
 }  

Solution 2: iterative BFS

 public class Solution {  
   public List<List<Integer>> levelOrder(TreeNode root) {  
     List<List<Integer>> res=new ArrayList<>();  
     if (root==null) return res;  
     Queue<TreeNode> q1=new LinkedList<>();  
     Queue<TreeNode> q2=new LinkedList<>();  
     q1.offer(root);  
     while (!q1.isEmpty()) {  
       List<Integer> one=new ArrayList<>();  
       while (!q1.isEmpty()) {  
         TreeNode x=q1.poll();  
         one.add(x.val);  
         if (x.left!=null) q2.offer(x.left);  
         if (x.right!=null) q2.offer(x.right);  
       }  
       res.add(one);  
       q1=q2;  
       q2=new LinkedList<>();  
     }  
     return res;  
   }  
 }  

Leetcode 101 Symmetric Tree

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

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

Solution 1: recursive

 public class Solution {  
   public boolean isSymmetric(TreeNode root) {  
     return dfs(root, root);  
   }  
   private boolean dfs(TreeNode x, TreeNode y) {  
     if (x==null && y==null) return true;  
     if (x==null || y==null) return false;  
     if (x.val!=y.val) return false;  
     return dfs(x.left, y.right) && dfs(x.right, y.left);  
   }  
 }  

Solution 2: iterative

 public class Solution {  
   public boolean isSymmetric(TreeNode root) {  
     Deque<TreeNode> s1=new LinkedList<>();  
     Deque<TreeNode> s2=new LinkedList<>();  
     TreeNode x=root, y=root;  
     while (x!=null || y!=null || !s1.isEmpty()) {//s1,s2 always pop.push same time  
       if (x!=null || y!=null) {  
         if (x==null || y==null) return false;  
         if (x.val!=y.val) return false;  
         s1.push(x);  
         s2.push(y);  
         x=x.left;  
         y=y.right;  
       }  
       else {  
         x=s1.pop();  
         y=s2.pop();  
         x=x.right;  
         y=y.left;  
       }  
     }  
     return true;  
   }  
 }  

Leetcode 100 Same Tree

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.

Solution 1: DFS, recursive

 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     return dfs(p,q);  
   }  
   private boolean dfs(TreeNode x, TreeNode y) {  
     if (x==null && y==null) return true;  
     if (x==null || y==null) return false;  
     if (x.val != y.val) return false;  
     return dfs(x.left, y.left) && dfs(x.right, y.right);  
   }  
 }  

Solution 1: DFS, iterative

 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     Deque<TreeNode> s1=new LinkedList<>();  
     Deque<TreeNode> s2=new LinkedList<>();  
     TreeNode x=p, y=q;  
     if (x==null && y!=null) return false; //corner case  
     while (x!=null || !s1.isEmpty()) {  
       if (x!=null) {  
         if (y==null) return false;  
         s1.push(x);  
         s2.push(y);  
         x=x.left;  
         y=y.left;  
       }  
       else {  
         if (y!=null) return false;  
         x=s1.pop();  
         y=s2.pop();  
         if (x.val!=y.val) return false;  
         x=x.right;  
         y=y.right;  
       }  
     }  
     return true;  
   }  
 }  

Leetcode 99 Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Solution 1: in order traversal, use stack though, but at the end stack is empty. Below is iterative way, recursive is simpler but use system stack, same thing. A real O(1) need Morris Traversal.

 public class Solution {  
   public void recoverTree(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     TreeNode p1=null, p2=null, pre=null, x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         if (pre!=null && pre.val>x.val) {  
           if (p1==null) {  
             p1=pre;  
             p2=x;// incase in sorted array p1,p2 is next to each other  
           }  
           else p2=x;  
         }  
         pre=x;  
         x=x.right;  
       }  
     }  
     int temp=p1.val;  
     p1.val=p2.val;  
     p2.val=temp;  
   }  
 }  

Leetcode 98 Validate Binary Search Tree

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.

Solution 1: Use node as low and high limit instead of use Integer.MAX_VALUE and Integer.MIN_VALUE.

 public class Solution {  
   public boolean isValidBST(TreeNode root) {  
     return dfs(root,null,null);  
   }  
   private boolean dfs(TreeNode x, TreeNode l, TreeNode r) {  
     if (x==null) return true;  
     if (l!=null && l.val>=x.val) return false;  
     if (r!=null && r.val<=x.val) return false;  
     return dfs(x.left,l,x) && dfs(x.right,x,r);  
   }  
 }  

Leetcode 97 Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution 1: Use DP, dp[i][j] store the result of s1[0...i) s2[0..j) and s3[0...i+j) is interleaving or not. There will be 2 case, s1.charAt(i-1)==s3.charAt(i+j-1) or s2.charAt(j-1)==s3.charAt(i+j-1). Details below:

 public class Solution {  
   public boolean isInterleave(String s1, String s2, String s3) {  
     int m=s1.length();  
     int n=s2.length();  
     if (m+n!=s3.length()) return false;  
     boolean[] dp=new boolean[n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (i==0) {  
           if (j==0) dp[j]=true;  
           else dp[j]=s2.charAt(j-1)==s3.charAt(j-1) && dp[j-1];  
         }  
         else if (j==0) dp[j]=s1.charAt(i-1)==s3.charAt(i-1) && dp[j];  
         else dp[j]=(s1.charAt(i-1)==s3.charAt(i+j-1) && dp[j]) || (s2.charAt(j-1)==s3.charAt(i+j-1) && dp[j-1]);  
       }  
     }  
     return dp[n];  
   }  
 }  

Leetcode 96 Submission Details

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

Solution 1: best way to use DP.

 public class Solution {  
   public int numTrees(int n) {  
     int[] dp=new int[n+1];  
     for (int i=0; i<=n; i++) {  
       if (i==0) dp[i]=1;  
       else {  
         for (int j=0; j<i; j++) dp[i]+=dp[j]*dp[i-1-j];  
       }  
     }  
     return dp[n];  
   }  
 }