110 Balanced Binary Tree

LeetCode

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 left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4] Output: false

Example 3:

Input: root = [] Output: true

Constraints:

The number of nodes in the tree is in the range [0, 5000]. -104 <= Node.val <= 104

---

递归，计算每个节点两子树的高度，如果相差超过1，则不是平衡树

class Solution {
    boolean isBal=true;
    public boolean isBalanced(TreeNode root) {
        height(root);
        return isBal;
    }
    
    private int height(TreeNode t){
        if(t==null) return 0;
        int height1=height(t.left);
        int height2=height(t.right);
        if(Math.abs(height1-height2)>1) isBal=false;
        return Math.max(height1,height2)+1;
    }
}

如果左子树递归完已经发现不是平衡树了，那么不必考虑右子树，不必真的计算高度（这样其实效率差不多）

class Solution {
    boolean isBal=true;
    public boolean isBalanced(TreeNode root) {
        height(root);
        return isBal;
    }
    
    private int height(TreeNode t){
        if(t==null) return 0;
        int height1=height(t.left);
        if(!isBal) return 0;
        int height2=height(t.right);
        if(Math.abs(height1-height2)>1) isBal=false;
        return Math.max(height1,height2)+1;
    }
}