Leetcode 110 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.

Solution 1: DFS recursive, O(n)

 public class Solution {  
   private boolean res;  
   public boolean isBalanced(TreeNode root) {  
     res=true;  
     dfs(root,0);  
     return res;  
   }  
   private int dfs(TreeNode x, int d) {  
     if (x==null) return d;  
     int left=dfs(x.left,d+1);  
     int right=dfs(x.right,d+1);  
     if (Math.abs(left-right)>1) res=false;  
     return Math.max(left,right);  
   }  
 }  

Attention is that BFS is not going to work.

Expected: true

            1
       2           2
    3     3     3     3 
  4  4   4 4   4 4   # # 
 5 5 

The balance definition is not the case, so below BFS iterative code can NOT pass above test case.

 public class Solution {  
   public boolean isBalanced(TreeNode root) {  
     Queue<TreeNode> q1=new LinkedList<>();  
     Queue<TreeNode> q2=new LinkedList<>();  
     if (root==null) return true;  
     int d=0;  
     Set<Integer> set=new HashSet<>();  
     q1.offer(root);  
     while (!q1.isEmpty()) {  
       while (!q1.isEmpty()) {  
         TreeNode x=q1.poll();  
         if (x.left==null) set.add(d+1);  
         else q2.offer(x.left);  
         if (x.right==null) set.add(d+1);  
         else q2.offer(x.right);  
       }  
       d++;  
       Queue<TreeNode> temp=q1;  
       q1=q2;  
       q2=temp;  
     }  
     return set.size()<=2;  
   }  
 }