Skip to content

面试题55 - II. 平衡二叉树

示例

js
示例 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

JS

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
    // 计算节点深度
    const treeDeep = function (node, n=0) {
        if (node) {
            let left = treeDeep(node.left, n + 1)
            let right = treeDeep(node.right, n + 1)
            return left > right ? left : right
        }
        return n
    }
    // 层序遍历判断
    const judge = function (node) {
        if (!node) {
            return true
        }
        let queue = []
        queue.push(node)
        while (queue.length !== 0) {
            let n = queue.shift()
            let l = treeDeep(n.left)
            let r = treeDeep(n.right)
            if (Math.abs(l - r) > 1) {
                return false
            }
            if (n.left) {
                queue.push(n.left)
            }
            if (n.right) {
                queue.push(n.right)
            }
        }
        return true
    }
    return judge(root)
};

题链