DataStructure_Algorithm_HandBook_PreForLeetCode

110. Balanced Binary Tree

height-balanced

Example 1:

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

Example 2:

110. Balanced Binary Tree

height-balanced

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

  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

solution

对于任意节点来说，左右子树高度不超过 1 就是平衡二叉树了 因此我们遍历每一个节点，判断其左右子树高度就可以了

class Solution {
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return res;
    }
    boolean res = true;
    int dfs(TreeNode node){
        if(node == null) return 0;
        int l = dfs(node.left); int r = dfs(node.right);
        if(Math.abs(r-l)>1) res=false;
        return Math.max(l,r) + 1;    
    }
}

剪枝优化，只要有一个节点不符合左右子树高度差，就直接返回

class Solution {
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return res;
    }
    boolean res = true;
    int dfs(TreeNode node){
        if(node == null || !res) return 0;
        int l = dfs(node.left); int r = dfs(node.right);
        if(Math.abs(r-l)>1) res=false;
        return Math.max(l,r) + 1;    
    }
}