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.

深度优先搜索

复杂度

时间 O(N) 空间 O(h) 递归栈空间

思路

非平衡的条件是有两个叶子节点的深度相差大于1，最直接的想法就是把左子树和右子树的高度都算出来，如果相差大于1则说明不是平衡的。在递归中，从叶子结点开始一层层返回高度，叶子结点是1。我们返回-1代表非平衡，返回自然数代表有效的子树高度。

代码

public class Solution {    public boolean isBalanced(TreeNode root) {        if(root==null) return true;        int left = findHeight(root.left);        int right = findHeight(root.right);        return left != -1 && right != -1 && Math.abs(left-right)<=1;    }        private int findHeight(TreeNode root){        if(root == null) return 0;        int left = findHeight(root.left);        int right = findHeight(root.right);        if(left == -1 || right == -1 || Math.abs(left-right) > 1) return -1;        return Math.max(left, right)+1;    }}