Same Tree, Symmetric Tree, Balanced Binary Tree, Binary Tree Level Order Traversal, Binary Tree Level Order Traversal II, Maximum Depth of Binary Tree, Minimum Depth of Binary Tree // Cici's Blog

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.

Recursive Solution

public boolean isSameTree(TreeNode p, TreeNode q) {
      if(p==null && q==null) return true;
      if(p!=null && q!=null && p.val==q.val){
          return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
      }
      return false;
  }

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:

But the following is not:

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

Recursive Solution

Just traverse both on left and right branches of the root symmetricaly and check if the values are equal.

public boolean isSymmetric(TreeNode root) {
     if(root==null) return true;
     return rec(root.left ,root.right);
 }
 
 private boolean rec(TreeNode l, TreeNode r){
     if(l==null && r==null) return true;
     else if(l!=null && r!=null && l.val==r.val) 
     return rec(l.left,r.right) && rec(l.right, r.left);
     else return false;
 }

Iterative Solution

Two Stacks to store the two partitions of nodes that are supposed to be equal.

public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        Stack<TreeNode> l=new Stack<TreeNode>();
        Stack<TreeNode> r=new Stack<TreeNode>();
        l.push(root.left);
        r.push(root.right);
        while(!l.isEmpty() && ! r.isEmpty()){
            TreeNode left=l.pop();
            TreeNode right=r.pop();
            if(left==null && right==null) continue;
            else if(left!=null && right!=null && right.val==left.val){
                l.push(left.left); l.push(left.right);
                r.push(right.right); r.push(right.left); 
            } 
            else return false;
        }
        return true;
    }

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Recursive Solution

Two Nested Recursive:

getheight returns the highest depths of current node

break and return false if two children’s height differ by more than 1

else continue checking for both children, until reached null node.

public boolean isBalanced(TreeNode root) {
      if(root==null) return true;
      if(Math.abs(getheight(root.left) - getheight(root.right)) > 1) return false;
      return isBalanced(root.left) && isBalanced(root.right);
  }
  
  private int getheight(TreeNode cur){
      if(cur==null) return 1;
      return 1+Math.max(getheight(cur.left), getheight(cur.right));
  }

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},

return its level order traversal as:

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

BFS Solution

use two queues to store all nodes on the current level and their children level, when current level queue is empty, go to the next level

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> curlevel=new LinkedList<TreeNode>();
        Queue<TreeNode> nextlevel=new LinkedList<TreeNode>();
        if(root==null) return res;
        curlevel.add(root);
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        while(!curlevel.isEmpty())
        {
            TreeNode cur=curlevel.poll();
            tmp.add(cur.val);
            if(cur.left!=null)
            nextlevel.add(cur.left);
            if(cur.right!=null)
            nextlevel.add(cur.right);
            
            if(curlevel.isEmpty()){
              curlevel=nextlevel;
              nextlevel=new LinkedList<TreeNode>();
              res.add(new ArrayList<Integer>(tmp));
              tmp.clear();
            }
        }
        return res;
    }

DFS Solution

recursively add new levels to the list, keep a variable height to track when to create new list:

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

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

return its bottom-up level order traversal as:

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

BFS Solution

Just reverse the result list at the end…

public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> curlevel=new LinkedList<TreeNode>();
        Queue<TreeNode> nextlevel=new LinkedList<TreeNode>();
        if(root==null) return res;
        curlevel.add(root);
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        while(!curlevel.isEmpty())
        {
            TreeNode cur=curlevel.poll();
            tmp.add(cur.val);
            if(cur.left!=null)
            nextlevel.add(cur.left);
            if(cur.right!=null)
            nextlevel.add(cur.right);
            
            if(curlevel.isEmpty()){
              curlevel=nextlevel;
              nextlevel=new LinkedList<TreeNode>();
              res.add(new ArrayList<Integer>(tmp));
              tmp.clear();
            }
        }
        ArrayList<ArrayList<Integer>> resnew=new ArrayList<ArrayList<Integer>>();
        for(int i=res.size()-1;i>=0;i--){
            resnew.add(res.get(i));
        }
        return resnew;
    }

Or More concise


public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
      ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
      Queue<TreeNode> curlevel=new LinkedList<TreeNode>();
      if(root==null) return res;
      curlevel.add(root);
      while(!curlevel.isEmpty())
      {
         int levelnum=curlevel.size();
         ArrayList<Integer> tmp = new ArrayList<Integer>();
         for(int i=0;i<levelnum;i++){
             if(curlevel.peek().left!=null) curlevel.offer(curlevel.peek().left);
             if(curlevel.peek().right!=null) curlevel.offer(curlevel.peek().right);
             tmp.add(curlevel.poll().val);
         }
         res.add(0,tmp);
      }
      
      return res;
  }

DFS Solution

int height=0;
   public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root){
    ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
    dfs(res, root,0);
    return res;
 }
 private void dfs( ArrayList<ArrayList<Integer>> res, TreeNode root, int height){
    if(root==null) return;
    if(height>=res.size()){
      res.add(0,new ArrayList<Integer>());
    }
    res.get(res.size()-height-1).add(root.val);
    dfs(res, root.left, height+1);
    dfs(res, root.right, height+1);
 }

Maximum Depth of Binary Tree

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.

DFS Solution

public int maxDepth(TreeNode root) {
    if(root==null) return 0;
    return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}

Iterative Solution

Use a List to store BFS nodes, and an extra node to keep track of the last node on current level:

public int maxDepth(TreeNode root) {
      int depth=0;
      if(root==null) return depth;
      LinkedList<TreeNode> q=new LinkedList<TreeNode>();
      q.offer(root);
      TreeNode levelend=root, tmp;
      while(!q.isEmpty()){
          tmp=q.poll();
          if(tmp.left!=null) q.offer(tmp.left);
          if(tmp.right!=null) q.offer(tmp.right);
          if(tmp==levelend){
              depth++;
              levelend=q.peekLast();
          }
      } return depth;
  }

Minimum Depth of Binary Tree

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.

DFS Solution

A little different from max path: when one child is null, return the other half, when both is null return 1

public int minDepth(TreeNode root) {
    if(root==null) return 0;
    if(root.left==null && root.right==null) return 1;
    if(root.left==null) return minDepth(root.right)+1;
    else if(root.right==null) return minDepth(root.left)+1;
    else return Math.min(minDepth(root.left), minDepth(root.right))+1;
}

BFS Solution

One List to store BFS nodes, one list to store depth, min path found when reached any leaf:

public int minDepth(TreeNode root) {
    if(root == null) return 0;
    int res=0;
    LinkedList<TreeNode> l=new LinkedList<TreeNode>();
    LinkedList<Integer> count=new LinkedList<Integer>();
    l.offer(root); count.offer(1);
    while(!l.isEmpty()){
        TreeNode tmp=l.poll();
        res=count.poll();
        if(tmp.left!=null){
            l.offer(tmp.left);
            count.offer(res+1);
        }
        if(tmp.right!=null){
            l.offer(tmp.right);
            count.offer(res+1);
            }
        if(tmp.left==null && tmp.right==null) return res;    
    } return 0;
}