开始
开始

二叉平衡树

110. 平衡二叉树(简单)

TIP

后序遍历二叉树

在遍历二叉树每个节点前都会遍历其左右子树

比较左右子树的深度，若差值大于1 则返回一个标记 -1表示当前子树不平衡

左右子树有一个不是平衡的，或左右子树差值大于1，则整课树不平衡

若左右子树平衡，返回当前树的深度（左右子树的深度最大值+1） 

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
  function traversal(node) {
    if (node === null) {
      return 0
    }
    const left = traversal(node.left)
    const right = traversal(node.right)
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
      return -1
    }
    return Math.max(left, right) + 1
  }

  return traversal(root) !== -1
};