题目地址

110. 平衡二叉树

题目概述

isBalanceTree

题目分析

左右子树高度差大于1返回false，这个需要递归到每一层

  1. 递归结束条件：root为空返回true，左右子树高度差值大于1返回false

  2. 递归每层做什么：计算左树、右树高度

  3. 递归返回：高度值

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int l = getDepth(root.left);
    int r = getDepth(root.right);
    if (Math.abs(l - r) > 1) {
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right);
}

public int getDepth(TreeNode x) {
    if (x == null) {
        return 0;
    }
    return Math.max(getDepth(x.left), getDepth(x.right)) + 1;
}