剑指 Offer 55 - II. 平衡二叉树
力扣题目链接[1]
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
「限制：」
0 <= 树的结点个数 <= 10000
思路：
本题是昨天题目的升级版。首先总结下数的深度的定义：树的深度等于左子树和右子树的最大值加一。而今天的题目是要判断某棵树是否为平衡二叉树。
根据定义，可以看出，只要任意左子树和右子树的深度的差值为 0 或者 1，那么该树就是平衡二叉树。
首先我们采用后序遍历进行遍历二叉树，这样做可以提前判断左右子树是否平衡，如果不平衡可以提前返回，省去了无效判断。
同时规定当二叉树不平衡时，返回一个特定值，这里返回-1。如果最终递归的返回值为-1，则意味着不平衡，否则意味着平衡。
后序遍历
代码语言：javascript复制/**
* @param {TreeNode} root
* @return {boolean}
*/
const recur = (node) => {
if (!node) return 0; // 当前节点不存在，则深度为0
let left = recur(node.left);
if (left === -1) return -1; // 左子树为-1，则提前返回
let right = recur(node.right);
if (right === -1) return -1; // 右子树为-1，则提前返回
return Math.abs(left - right) < 2 ? Math.max(left, right) 1 : -1;
}
const isBalanced = (root) => {
return recur(root) !== -1; // 判断递归返回值是否为-1
};
- 时间复杂度 O(n)。
- 空间复杂度 O(n)。
分析：
本解法的返回值分为两种，一种是返回当前节点的深度，另一种是返回不平衡的特定值-1。
首先来看后序遍历的逻辑。
当前节点为空时，则深度为0。然后递归判断左子树，如果左子树不平衡，则直接提前返回。然后递归判断右子树，如果右子树不平衡，则直接提前返回。
如果左右子树都平衡，就判断当前节点是否平衡。判断的标准就是左子树的深度与右子树的深度的差值是否小于2，如果满足该条件，则直接返回当前节点的深度，否则返回-1提前返回。
最后就是主函数调用递归函数，然后判断返回值是否等于-1，如果不等于-1则意味着平衡。
复杂度方面，最差情况下，需要遍历所有节点，因此时间复杂度是O(n)。最差情况下，需要O(n)函数调用栈空间。
先序遍历
本题还可以通过先序遍历进行求解。
判断当前节点是否平衡，然后递归判断节点的左右子树是否平衡。计算当前节点的深度采用昨天题解的 DFS 解法。
代码语言：javascript复制/**
* @param {TreeNode} root
* @return {boolean}
*/
const depth = (node) => {
if (!node) return 0;
return Math.max(depth(node.left), depth(node.right)) 1;
}
const isBalanced = (root) => {
if (!root) return true;
return Math.abs(depth(root.left) - depth(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right)
};
- 时间复杂度 O(nlogN)。
- 空间复杂度 O(N)。
分析：
先序遍历判断二叉树是否平衡的逻辑为：
如果当前节点不存在，则意味着当前节点是平衡的。如果当前节点存在，则判断左右子树的深度相差是否小于 2，用来判断当前节点是否平衡。并递归判断左右子树是否是平衡。
先序遍历的方式会产生重复的判断，因此时间复杂度比后序遍历的高。
总结
本题分别使用先序遍历和后序遍历进行题解。后序遍历的效率比先序遍历的效率高，优先考虑使用后序遍历。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9hzffg/
