39-平衡二叉树

题目描述

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

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

分析

平衡二叉树(AVL树)：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

1. 遍历每个节点左右深度，看相差超不超过1。
2. 但是上面的做法会重复遍历很多遍结点，这样很浪费时间效率，正确方法只是遍历一遍，用后序遍历的方法遍历二叉树每个节点，那么在遍历一个结点前就已经遍历了他们的左、右子树，只要在遍历每个节点的时候记录它的深度，那么就可以一边遍历一边判断每个节点是不是平衡的。

代码

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function IsBalanced_Solution(pRoot)
{
   if(pRoot==null) return true;
   
   return Math.abs(getHeight(pRoot.left)-getHeight(pRoot.right))<=1;
    
}
function getHeight(node){
    if(node == null) return 0;
    if(node.left ==null && node.right == null) return 1;
    return Math.max(getHeight(node.left),getHeight(node.right))+1;
}