剑指Offer题解 - Day40

剑指 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，则意味着不平衡，否则意味着平衡。

后序遍历

/**
 * @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 解法。

/**
 * @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/