Leetcode题解之 —— 判断平衡二叉树

思路

DFS算法
先序遍历

题解

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
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function getHeight(root) {
  if (!root) {
    return 0;
  }
  const leftH = getHeight(root.left);
  const rightH = getHeight(root.right);

  return Math.max(leftH, rightH) + 1;
}

var isBalanced = function (root) {
  if (!root) {
    return true;
  }

  const leftH = getHeight(root.left);
  const rightH = getHeight(root.right);

  if (Math.abs(leftH - rightH) > 1) {
    return false;
  }

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