1. 题目描述

判断一棵树是不是平衡二叉树。

2. 思路分析

思路一：计算出左右子树的深度，然后检查差。递归继续判断左子树和右子树是不是平衡二叉树。

思路二：先计算左子树和右子树是不是平衡二叉树，然后再计算本身是不是平衡二叉树。

关于思路二为什么能比思路一更好，请看代码。

3. 代码实现

3.1 树的深度

先递归实现树的深度函数：

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
class Node {
    /**
     *
     * @param {Number} value
     * @param {Node} left
     * @param {Node} right
     */
    constructor(value, left, right) {
        this.value = value
        this.left = left
        this.right = right
    }
}

/**
 * 获取二叉树的深度
 *
 * @param {Node} root
 */
function treeDepth(root) {
    if (!root) {
        return 0
    }

    const leftDepth = treeDepth(root.left)
    const rightDepth = treeDepth(root.right)
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1
}

3.2 思路一

这种思路慢是因为：节点被重复计算了。得出 leftDepth 计算了一遍 root.left ，最后还要再调用自身计算 root.left。尤其是叶子节点，会造成很多的计算浪费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 判断是否是平衡二叉树
 *
 * @param {Node} root
 */
function isBalanced(root) {
    if (!root) {
        return true
    }

    const leftDepth = treeDepth(root.left)
    const rightDepth = treeDepth(root.right)
    const diff = Math.abs(leftDepth - rightDepth)
    if (diff > 1) {
        return false
    }

    return isBalanced(root.left) && isBalanced(root.right)
}

3.3 思路二

先遍历和计算左右子树，最后计算本身。不需要重复计算。

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
/**
 * 优化：判断是否是平衡二叉树
 *
 * @param {Node} root
 * @param {Object} obj
 */
function isBalanced2(root, obj = {}) {
    if (!root) {
        obj.depth = 0
        return true
    }

    const left = {},
        right = {}
    if (isBalanced2(root.left, left) && isBalanced2(root.right, right)) {
        const diff = Math.abs(left.depth - right.depth)
        if (diff > 1) {
            return false
        }

        obj.depth = 1 + (left.depth > right.depth ? left.depth : right.depth)
        return true
    } else {
        return false
    }
}

3.4 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 测试代码
 */
const root = new Node(1, new Node(2, new Node(4), new Node(5, new Node(7))), new Node(3, null, new Node(6)))

// 测试树的深度
console.log(treeDepth(root)) // output: 4

// 判断是否是平衡二叉树
console.time()
console.log(isBalanced(root)) // true
console.timeEnd() // 0.594ms

// 优化算法：判断是否是平衡二叉树
console.time()
console.log(isBalanced2(root)) // true
console.timeEnd() // 0.242ms