剑指 Offer 55 - II. 平衡二叉树

Posted on | In
Words count in article: 189 | Reading time ≈ 1

题目

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例1：

给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
3
   / \
  9  20
    /  \
   15   7

返回TRUE 。

示例2：

给定二叉树 [1,2,2,3,3,null,null,4,4]

1
2
3
4
5
6
7
1
     / \
    2   2
   / \
  3   3
 / \
4   4

返回 false 。

提示：

  • 节点总数 <= 10000

解法

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isBalanced(TreeNode root) {
        if (Objects.isNull(root)) {
            return true;
        }
        if (Math.abs(travel(root.left) - travel(root.right)) <= 1) {
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }

    private int travel(TreeNode root) {
        if (Objects.isNull(root)) {
            return 0;
        }
        return Math.max(travel(root.left), travel(root.right)) + 1;
    }
0%