平衡二叉树

链接：https://leetcode.cn/problems/balanced-binary-tree/
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 :::info 示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。 :::

思路

解法一

要满足一个树是平衡二叉树，它的子树也必须是平衡二叉树。我们可以从根结点开始，通过递归来求得子树的高度，以及子树是否是平衡二叉树，以此来结合判断二叉树是否是平衡二叉树。

var isBalanced = function(root) {
    if (!root) return true;
    let isSonBalanced = Math.abs(getHeight(root.left)  - getHeight(root.right)) <= 1;
    return isSonBalanced && isBalanced(root.left) && isBalanced(root.right);
};
const getHeight = (node) => {
    if (!node) return 0;
    return Math.max(getHeight(node.left), getHeight(node.right)) + 1
}

解法二

在解法一中，自顶向下地计算子树高度，这样导致了每层的高度都要重复计算。
为了解决这个问题，我们可以采用后续遍历的方法去求解，这样每个节点的高度就能根据前面的结果算出来。

var isBalanced = function(root) {
    return getHeight(root) !== -1;
};
const getHeight = (node) => {
    if (!node) return 0;
    const left = getHeight(node.left);
    const right = getHeight(node.right);
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
        return -1;
    }
    return Math.max(left, right) + 1;
}