SOURCE

// 思路
// 不推荐用迭代实现 会有很多重复操作
// 平衡二叉树定义
// 任意 节点的 左右子树 高度差 不大于1
// 而任意节点要对比左右子树才能得到结果 因此递归只适用后序遍历左右中
// 先得到左右子节点结果 才得出 包含当前节点 的 子树 结果

class Node {
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

let n2 = new Node(2, null, null);
let n2_2 = new Node(2, null, null);
let n1 = new Node(1, null, n2);
let n1_2 = new Node(1, n2_2, null);
let n4 = new Node(4, null, null);
let n4_2 = new Node(4, null, null);
let n3 = new Node(3, n4, n1);
let n3_2 = new Node(3, n1_2, n4_2);
let root = new Node(5, n3, n3_2);

function fn(root) {
    function 对比(node) {
        // 递归出口 递归到空节点时返回0
        if (node === null) return 0

        // 后序遍历
        let 左子树高度 = 对比(node.left)
        // 左/右子树高度为 -1 时 表示子树不是平衡二叉树
        // 说明当前节点不可能是平衡二叉树 向上传递结果
        if (左子树高度 === -1) return -1

        let 右子树高度 = 对比(node.right)
        // 左子树是平衡二叉树 判断右子树
        if (右子树高度 === -1) return -1

        // 左右子树都符合平衡二叉树
        // 则计算 包含当前节点 的子树 是否为平衡二叉树
        if (Math.abs(左子树高度 - 右子树高度) > 1) {
            // 左右子树高度差大于1 说明不是平衡二叉树
            return -1
        } else {
            // 高度差不大于1 说明包含当前节点的子树 是平衡的
            // 向上返回 包含当前节点 的子树 高度
            // 注意 取最长的一条边 + 1
            return 1 + Math.max(左子树高度, 右子树高度)
        }
    }
    return 对比(root) !== -1 ? '是平衡二叉树' : '不是平衡二叉树'
}

// 验证
console.log('是否为平衡二叉树？ 答:' + fn(root)) // 是平衡二叉树