My code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        return getDepth(root) == -1 ? false : true;
    }
    
    private int getDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = getDepth(root.left);
        if (left == -1)
            return -1;
        
        int right = getDepth(root.right);
        if (right == -1)
            return -1;
        
        if (Math.abs(left - right) < 2)
            return 1 + Math.max(left, right);
        else
            return -1;
        
    }
}

My test result:

Paste_Image.png

題目是easy級(jí)別，但可能，深夜，我太累了，腦子轉(zhuǎn)不過來，于是就沒寫出來。
本來不打算寫這道題目的，但還想拼一下，就寫了。
題目本身也是需要想想的。
具體看這個(gè)博客吧。
http://bangbingsyb.blogspot.com/2014/11/leetcode-balanced-binary-tree.html

我想說明的是，什么 depth of tree and height of tree
depth of node n: length of path from n to root.
所以說， depth of subtree 指的應(yīng)該就是 這棵subtree最大的深度，以該subtree結(jié)點(diǎn)為root。
所以， balanced binary tree的左右subtree的最大深度，不能超過1.
然后這個(gè)規(guī)則繼續(xù)遞歸給subtree的左右subtree。
然后需要bottom-up 來進(jìn)行判斷。具體看代碼吧。
還有就是，
height of node n: length of path from n to its deepest descendent.
= depth of the subtree.

**
總結(jié)： Tree, DFS, Balance binary tree, depth of tree, height of tree
**

Anyway, Good luck, Richardo!

My code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        return helper(root) == -1 ? false : true;
    }
    
    /** if return -1, means it is not balanced */
    private int helper(TreeNode root) {
        if (root == null)
            return 0;
        int left = helper(root.left);
        if (left == -1)
            return -1;
        int right = helper(root.right);
        if (right == -1)
            return -1;
        if (Math.abs(left -right) <= 1)
            return Math.max(left, right) + 1;
        else 
            return -1;
    }
}

這道題目是從下往上的dfs

cf聊了那么多家，投了那么多家，竟然一家都沒給機(jī)會(huì)。。
不再畏懼了。沒什么準(zhǔn)備不準(zhǔn)備的。
海投，開始吧！
剛把a(bǔ)pple投了。

Anyway， Good luck, Richardo!

My code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        int ret = helper(root);
        return ret == -1 ? false : true;
    }
    
    private int helper(TreeNode root) {
        if (root.left == null && root.right == null) {
            return 1;
        }
        else if (root.left == null) {
            int right = helper(root.right);
            if (right == -1 || right > 1) {
                return -1;
            }
            else {
                return 1 + right;
            }
        }
        else if (root.right == null) {
            int left = helper(root.left);
            if (left == -1 || left > 1) {
                return -1;
            }
            else {
                return 1 + left;
            }
        }
        else {
            int left = helper(root.left);
            int right = helper(root.right);
            if (left == -1 || right == -1) {
                return -1;
            }
            else if (Math.abs(left - right) > 1) {
                return -1;
            }
            else {
                return 1 + Math.max(left, right);
            }
        }
    }
}

差不多的思路。

Anyway, Good luck, Richardo! -- 08/28/2016