LeetCode110-平衡二叉树

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/balanced-binary-tree/

中文链接：https://leetcode-cn.com/problems/balanced-binary-tree/

题目详述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 。

题目详解

  • 实现计算二叉树深度的方法。
  • 比较当前结点的左右子树的深度差的绝对值是否大于 1。
    • 大于 1 说明不平衡。
    • 小于或等于 1 需要判断它的左子树和右子树是否平衡，只有它们都平衡时才是一颗平衡二叉树。判断左子树和右子树是否平衡进行递归调用即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00110 {

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(depth(root.left) - depth(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(depth(root.left), depth(root.right));
    }
}

上面的递归调用存在很多重复计算，如果我们在计算深度的过程发现子树不平衡，那么整棵树就是不平衡的，不需要再继续判断。

  • 修改 depth 方法返回值定义。
    • 当它返回 >=0 的值时是二叉树的深度。
    • 当它返回 -1 的值时说明二叉树不平衡。
  • 如果在计算深度的过程中，发现返回值为 -1，就不需要再计算了，直接返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00110 {

    public boolean isBalanced(TreeNode root) {
        return depth(root) != -1;
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = depth(root.left);
        if (leftDepth == -1) {
            return -1;
        }
        int rightDepth = depth(root.right);
        if (rightDepth == -1) {
            return -1;
        }
        return Math.abs(leftDepth - rightDepth) > 1 ? -1 : 1 + Math.max(leftDepth, rightDepth);
    }
}