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

示例

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

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

题链