[LeetCode]Balanced Binary Tree

Question
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.

---

本题难度Easy。

DFS

【复杂度】
时间 O(N) 空间 O(h) 递归栈空间

【思路】
利用DFS分别算出左右子树的深度，然后比较看两个子树的深度之差是否超过1，超过则说明不平衡。在递归中，从叶子结点开始一层层返回高度，叶子结点是1。我们返回-1代表不平衡，返回自然数代表有效的子树高度。

【附】
为了提高效率，会先判断两个子树的返回值是否为-1。

【代码】

/**
 * 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(helper(root)==-1)
            return false;
        else
            return true;
    }
    private int helper(TreeNode root){
        //base case
        if(root==null)
            return 0;

        int left=helper(root.left);
        if(left==-1)return left;
        int right=helper(root.right);
        if(right==-1)return right;
        if(Math.abs(left-right)>1)
            return -1;
        else
            return Math.max(left,right)+1;
    }
}

参考

​​[LeetCode]Maximum Depth of Binary Tree​​