平衡二叉树

发表于 | 分类于

题目

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路

递归
判断左右子树相差为多少

代码

1
2
3
4
5
6
7
8
9
10
11
12
function IsBalanced_Solution(pRoot) {
  if (pRoot == null) return true;
  let leftLen = TreeDepth(pRoot.left);
  let rightLen = TreeDepth(pRoot.right);
  return Math.abs(rightLen - leftLen) <= 1 && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
}
function TreeDepth(pRoot) {
  if (pRoot == null) return 0;
  let leftLen = TreeDepth(pRoot.left);
  let rightLen = TreeDepth(pRoot.right);
  return Math.max(leftLen, rightLen) + 1;
}