110. Balanced Binary Tree (DFS) 20.3.16 Easy

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]:

    3
   / \
  9  20
    /  \
   15   7
Return true.

Example 2:

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

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
Return false.

Solution: ------------------------------------------------------------- https://www.youtube.com/watch?v=Be5CUodZliM
------------------------------------------------ O(N) T, O(N) S
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
'''
递归问题：
找到任意一个节点，假设下一层已经解决了，再研究这个问题该怎么解，该怎么把有效信息传递到上一层（假设下一层已经完成），然后再考虑边界条件。
'''
class Solution(object):
    def isBalanced(self, root):
        if root is None:                             
            return True
        res = self.dfs_helper(root)
        return res != -1
        """
        :type root: TreeNode
        :rtype: bool
        """
    def dfs_helper(self, root):
        if not root:
            return 0
        else:
            depth_left = self.dfs_helper(root.left)
            depth_right = self.dfs_helper(root.right)
            if depth_left == -1 or depth_right == -1 or abs(depth_left - depth_right) > 1: # -1 stands for the tree under it is not
                                                                                           # balance tree
                return -1
            '''
            DO NOT WRITE:
            if self.dfs_helper(root.left) == -1 or self.dfs_helper(root.right) == -1 
            or abs(self.dfs_helper(root.left) - self.dfs_helper(root.right)) > 1:
            BECAUSE IT WILL CAUSE TIME LIMIT EXCEED!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            DO IT ONCE BY A TIME SO THAT THE COMPUTER WILL NOT GET CONFUSED BETWEEN CALLING THE FUNCTIONS AND DO OR LOGIC DECISION!!!!
            '''
            else:
                return max(depth_left, depth_right) + 1    # "+ 1" is the key in this algorithm that connecting inside the recursion


Java Version:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (dfs(root) != -1) {
            return true;
        } else {
            return false;
        }
    }
    
    public int dfs(TreeNode currNode) {
        if (currNode == null) {
            return 0;
        }
        int leftDepth = dfs(currNode.left);
        int rightDepth = dfs(currNode.right);
        if (leftDepth == -1 || rightDepth == -1) {
            return -1;
        } else {
            if (Math.abs(leftDepth - rightDepth) > 1) {
                return -1;
            } else {
                return Math.max(leftDepth, rightDepth) + 1;
            }
        }
    }
}