Massive Algorithms: LeetCode 110

https://leetcode.com/problems/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.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

Return false

https://discuss.leetcode.com/topic/7798/the-bottom-up-o-n-solution-would-be-better

2.The second method is based on DFS. Instead of calling depth() explicitly for each child node, we return the height of the current node in DFS recursion. When the sub tree of the current node (inclusive) is balanced, the function dfsHeight() returns a non-negative value as the height. Otherwise -1 is returned. According to the leftHeight and rightHeight of the two children, the parent node could check if the sub tree is balanced, and decides its return value.

https://discuss.leetcode.com/topic/32793/easy-top-down-bottom-up-beat-89-35-solutions-in-java

https://discuss.leetcode.com/topic/20394/a-clean-and-fast-dfs-approach/2

If ld is negative, then you should return without executing the left recursive call.

it'd be better shortcircuited.

https://discuss.leetcode.com/topic/44051/java-1ms-solution-with-explanation

    public boolean isBalanced(TreeNode root) {
        return checkBalance(root) == -1 ? false : true;
    }
    
    // 1. If a subtree is hit as unbalanced, the whole tree is unbalanced. In this case, -1 is set as the return value.
    // 2. If the left subtree and the right subtree of a node are balanced, there are two more cases:
    // 2.1. The tree rooted at the node is unbalanced (the depth of its two subtrees differs by more than 1), as a result, -1 is returned.
    // 2.2 The tree rooted at the node is balanced, then the depth of the tree will be returned.
    public int checkBalance(TreeNode node){
        if (node == null) // case 2.2
            return 0;
            
        int left = checkBalance(node.left);
        if (left == -1) // check case 1
            return -1;
            
        int right = checkBalance(node.right);
        if (right == -1) // check case 1
            return -1;
        
        if (left - right > 1 || right - left > 1)
            return -1; // check case 2.1
        
        return (left > right ? left : right) + 1; // case 2.2
    }

Bottom Up Solution, which is O(n) time complexity

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

www.programcreek.com/2013/02/leetcode-balanced-binary-tree-java/

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

https://discuss.leetcode.com/topic/3746/accepted-on-solution

We determine recursively the height of the root node but when the recursion is coming upwards we return UNBALANCED instead of the actual height if we know that the tree is already known to be unbalanced.

We visit each node just once thus it has linear time complexity.

private static final int UNBALANCED = -99;

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    return getHeight(root) != UNBALANCED;
}

private int getHeight(TreeNode root) {
    if (root == null) {
        return -1;
    }
    int l = getHeight(root.left);
    int r = getHeight(root.right);
    if (l == UNBALANCED || r == UNBALANCED || Math.abs(l-r) > 1) {
        return UNBALANCED;
    }
    return 1 + Math.max(l,r);
}

X. https://discuss.leetcode.com/topic/3323/use-exception-handling-to-early-terminate-and-return-once-a-unbalance-is-found

    public boolean isBalanced(TreeNode root) {
        try {
            getDepth(root);
        } catch (Exception e) {
            return false;
        }
        return true;
    }
    private int getDepth(TreeNode root) throws Exception {
        if (root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1) {
            throw new Exception("Not balanced!");
        }
        return Math.max(leftDepth, rightDepth) + 1;
    }

X. Iterative version
https://discuss.leetcode.com/topic/9346/a-iterative-postorder-traversal-java-solution

    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if((node.left==null || node.left!=null && map.containsKey(node.left)) &&(node.right==null || node.right!=null && map.containsKey(node.right))){
                int left = node.left==null?0:map.get(node.left);
                int right = node.right==null?0:map.get(node.right);
                if(Math.abs(left-right) > 1) return false;
                map.put(node, Math.max(left, right)+1);
            }else{
                if(node.left!=null && !map.containsKey(node.left)){
                    stack.push(node);
                    stack.push(node.left);
                }else{
                    stack.push(node);
                    stack.push(node.right);
                }
            }
        }
        return true;
    }
}

http://n00tc0d3r.blogspot.com/2013/01/determine-height-balanced-binary-tree.html
Attempt 1: The basic logic of isBalanced(root) could be:

Find out the depths of left and right subtrees;
If it is not balanced (i.e. abs(depLeft - depRight) > 1), return false;
Otherwise, return isBalanced(root.left) && isBalanced(root.right);

Of course, we need a base case so that recursion can terminate: return true if it is an empty tree (i.e. root == null).

This seems fine and it works. But, think about it more carefully: Starting from root, we trace down to its left and right subtrees to get the depth, do the calculation, then in the next recursion, we go to its left and right child, repeat the same process (and revisit all children nodes!). That is, we need to access each node multiple times. More specifically, suppose we have a full binary tree of height k,

in top level, we visit each node once;
in 2nd level, visit twice;
...
in (k-1)-th level, visit (k-1) times;
in k-th level, visit k time.

In total, we have T = k*(n/2), where n is the total number of nodes in the tree. We know k = log(n/2) = O(logn). So, this algorithm runs in time O(nlogn).

Can we do better? When we try to calculate the depth recursively, can we reuse any information without revisit?

http://blog.csdn.net/fightforyourdream/article/details/18693131

 public boolean isBalanced(TreeNode root) {
        if(root == null){
         return true;
        }
        // 如果子树高度差大于1，则不平衡
        if(Math.abs(depth(root.left)-depth(root.right)) > 1){
         return false;
        }
        // 递归检查左子树和右子树的平衡性
        return isBalanced(root.left) && isBalanced(root.right);
    }
 // 帮助方法，返回树的高度
 private int depth(TreeNode root){
  if(root == null){
   return 0;
  }
  return 1 + Math.max(depth(root.left), depth(root.right));
 }

Attempt 2: In the helper function, getDepth(root):

(base case) If it is an empty tree, return 0;
Find out the depth of left and right subtrees, recursively;
If it is not balanced or subtrees are not balanced, return a special value as a flag to pass back to upper levels;
Otherwise, return the depth of the tree;

Notice that the difference from attempt 1 is that this time we check the balance along the way to calculate the depth of the tree. So, we don't need to revisit the nodes.

Since we visit each node constant times, this algorithm runs in time O(n) and use O(n) space for recursion.

10:    private int getHeight(TreeNode root) {  
11:      if (root == null) return 0;  
12:      int depL = getHeight(root.left);  
13:      int depR = getHeight(root.right);  
14:      if (depL < 0 || depR < 0 || Math.abs(depL - depR) > 1) return -1;  
15:      else return Math.max(depL, depR) + 1;  
16:    }  
17:    public boolean isBalanced(TreeNode root) {  
18:      return (getHeight(root) >= 0);  
19:    }

http://www.jiuzhang.com/solutions/balanced-binary-tree/

// Version 1: with ResultType
class ResultType {
    public boolean isBalanced;
    public int maxDepth;
    public ResultType(boolean isBalanced, int maxDepth) {
        this.isBalanced = isBalanced;
        this.maxDepth = maxDepth;
    }
}

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) {
        return helper(root).isBalanced;
    }
    
    private ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(true, 0);
        }
        
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        
        // subtree not balance
        if (!left.isBalanced || !right.isBalanced) {
            return new ResultType(false, -1);
        }
        
        // root not balance
        if (Math.abs(left.maxDepth - right.maxDepth) > 1) {
            return new ResultType(false, -1);
        }
        
        return new ResultType(true, Math.max(left.maxDepth, right.maxDepth) + 1);
    }
}

X. Use global variable
https://discuss.leetcode.com/topic/10192/java-o-n-solution-based-on-maximum-depth-of-binary-tree

private boolean result = true;

public boolean isBalanced(TreeNode root) {
    maxDepth(root);
    return result;
}

public int maxDepth(TreeNode root) {
    if (root == null)
        return 0;
    int l = maxDepth(root.left);
    int r = maxDepth(root.right);
    if (Math.abs(l - r) > 1)
        result = false;
    return 1 + Math.max(l, r);
}

for each node,the two subtrees differ in height by no more than one. We can implement a solution based on this definition.
We can simply recurse through the entire tree, and for each node, compute the heights of each subtree

X. O(N^2)
https://discuss.leetcode.com/topic/1278/can-we-have-a-better-solution

public boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;
    if (Math.abs(depth(root.left) - depth(root.right)) >1)
        return false;
    return isBalanced(root.left) && isBalanced(root.right);
}

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

Although this works. it's not very efficient. On each node. we recurse through its entire subtree. This means that getHeight is called repeatedly on the same nodes. The algorithm isO(N log N) since each node is"touched" once per node above it.

This code runs in O(N) time and O(H) space, where H is the height of the tree.

If we inspect this method, we may notice that getHeight could actually check if the tree is balanced at

the same time as it's checking heights. What do we do when we discover that the subtree isn' t balanced?

Just return an error code.

This improved algorithm works by checking the height of each subtree as we recurse down from the root.

On each node, we recursively get the heights of the left and right subtrees through the checkHeight

method. If the subtree is balanced, then checkHeight will return the actual height of the subtree. If the

subtree is not balanced, then c h ec kHeight will return an error code. We will immediately break and

return an error code from the current call.

I What do we use for an error code? The height of a null tree is generally defined to be -1, so that's

not a great idea for an error code. Instead, we' ll use Integer. MIN_ VALUE.

int checkHeight(TreeNode root) {
if (root == null) return -1;

int leftHeight = checkHeight(root.left);
if (leftHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE; // Pass error up

int rightHeight = checkHeight(root.right);
if (rightHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE; // Pass error up

int heightDiff = leftHeight - rightHeight;
if (Math.abs(heightDiff) > 1) {
return Integer.MIN_VALUE; // Found error -> pass it back
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}

boolean isBalanced(TreeNode root) {
return checkHeight(root) != Integer.MIN_VALUE;
}
Read full article from 水中的鱼: [LeetCode] Balanced Binary Tree Solution

LeetCode 110 - Balanced Binary Tree

Labels

Popular Posts