LeetCode 110. 平衡二叉树 剪枝题解，先有暴力递归解，再有后序遍历优化。
110. 平衡二叉树#
https://leetcode.cn/problems/balanced-binary-tree/
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
从上往下求深度#
树形遍历，我最先想到的是DFS，同时题干给出了定义。
不难写出定义判定公式：
1
|
Math.abs(depth(root.left, 0) - depth(root.right, 0)) <= 1
|
同时平衡是否同样适用于父节点的左右子树。
复杂度分析#
此解法需递归计算子树深度，同时会在每个节点上重复遍历。复杂度O(n^2)。
递归栈为主要空间开销，树退化为链表时，栈正好为节点数长度，空间复杂度O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
static class UpToDown {
/**
* 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
*
* @return abs(h ( root.left)-h(root.right))<=1
*/
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return Math.abs(depth(root.left, 0) - depth(root.right, 0)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode node, int h) {
if (node == null) {
return h;
}
return Math.max(depth(node.left, h + 1), depth(node.right, h + 1));
}
}
|
从下往上求高度#
解法1可以看到时间复杂度很高。因为有重复计算。
树形遍历，一定有办法剪枝。
我们可以学习后序遍历的思路，每次先处理子树，最后处理当前父节点，这样每个父节点实际只会计算一次高度。
同时在某一层如果已经判断左右子树不平衡，整个函数也可以提前返回。
复杂度分析#
后序遍历，整个树只会下去之后再上去一遍。复杂度O(n)。
同解法1空间开销，空间复杂度O(n)。
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
30
31
32
33
|
static class DownToUp {
/*
* 从下往上算
* h 函数负责计算当前节点高度
* -1表示非平衡二叉树的高度，作为特判
*/
public boolean isBalanced(TreeNode root) {
return h(root) != -1;
}
/**
* 从下往上处理，即后序遍历，先处理左右子树，最后处理当前节点
*/
private int h(TreeNode parent) {
if (parent == null) {
return 0;
}
int hLeft = h(parent.left);
if (hLeft == -1) {
return -1;
}
int hRight = h(parent.right);
if (hRight == -1) {
return -1;
}
if (Math.abs(hLeft - hRight) > 1) {
return -1;
}
// 父节点高度为左右子树高度较大值+1
return Math.max(hLeft, hRight) + 1;
}
}
|
可以看到解法2效率更高，解法1则代码更加简洁。