Leetcode - Balanced Binary Tree

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级别，但可能，深夜，我太累了，脑子转不过来，于是就没写出来。
本来不打算写这道题目的，但还想拼一下，就写了。
题目本身也是需要想想的。
具体看这个博客吧。
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 指的应该就是这棵subtree最大的深度，以该subtree结点为root。
所以， balanced binary tree的左右subtree的最大深度，不能超过1.
然后这个规则继续递归给subtree的左右subtree。
然后需要bottom-up 来进行判断。具体看代码吧。
还有就是，
height of node n: length of path from n to its deepest descendent.
= depth of the subtree.

**
总结： 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聊了那么多家，投了那么多家，竟然一家都没给机会。。
不再畏惧了。没什么准备不准备的。
海投，开始吧！
刚把apple投了。

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

Leetcode - Balanced Binary Tree

推荐阅读更多精彩内容