平衡二叉树

发表于 | 分类于 |
字数统计: 1.2k 字 | 阅读时长 ≈ 5 分钟

题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。

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

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：
img
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
img
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：
输入：root = []
输出：true

方法一：自底向上

相当于后序遍历

此方法为本题的最优解法，但“从底至顶”的思路不易第一时间想到。

思路是对二叉树做后序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

算法流程：
height(root):

  • 递归返回值：
    1. 当节点root 左 / 右子树的高度差 > 1 ：则返回 −1 ，代表 此子树不是平衡树。
    2. 当节点root 左 / 右子树的高度差 <= 1 ：则返回以节点root为根节点的子树的最大高度，即节点 root 的左右子树中最大高度加 1（ max(left, right) + 1 ）
  • 递归终止条件：
    1. 当越过叶子节点时，返回高度 0 ；
    2. 当左（右）子树高度 left== -1 时，代表此子树的 左（右）子树 不是平衡树，因此直接返回 -1 ；

isBalanced(root) ：

  • 返回值： 若 height(root) != 1 ，则说明此树平衡，返回 true ； 否则返回 false 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public boolean isBalanced(TreeNode root) {
    return height(root) >= 0;
  }

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

复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。

  • 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。

方法二：自顶向下

相当于前序遍历

此方法容易想到，但会产生大量重复计算，时间复杂度较高。

思路是构造一个获取当前节点最大深度的方法 height(root) ，通过比较此子树的左右子树的最大高度差abs(height(root.left) - height(root.right))，来判断此子树是否是二叉平衡树。若树的所有子树都平衡时，此树才平衡。

算法流程：
isBalanced(root) ：判断树 root 是否平衡

  • 特例处理： 若树根节点 root 为空，则直接返回 true ；
  • 返回值： 所有子树都需要满足平衡树性质，因此以下三者使用与逻辑 && 连接；
    1. abs(self.height(root.left) - self.height(root.right)) <= 1 ：判断 当前子树 是否是平衡树；
    2. self.isBalanced(root.left) ： 先序遍历递归，判断 当前子树的左子树 是否是平衡树；
    3. self.isBalanced(root.right) ： 先序遍历递归，判断 当前子树的右子树 是否是平衡树；

depth(root) ： 计算树 root 的最大高度

  • 终止条件： 当 root 为空，即越过叶子节点，则返回高度 0 ；
  • 返回值： 返回左 / 右子树的最大高度加 1 。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
  public boolean isBalanced(TreeNode root) {
    if(root == null) return true;
    return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
  }

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

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 是二叉树中的节点个数。
    最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)。
    对于节点 p，如果它的高度是 d，则 height(p) 最多会被调用 d 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 h 满足 O(h)=O(logn)，因为 d≤h，所以总时间复杂度为 O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2)。（白话：要不断递归左右子树，有重复部分）

  • 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了96.94%的用户

  • 内存消耗：38.6 MB, 在所有 Java 提交中击败了31.56%的用户