判断是不是平衡二叉树

function IsBalanced_Solution(pRoot)
{
    // write code here
    let flag=true
    if(!pRoot)return true
    function height(root){
        if(!root) return  0
        let l=height(root.left)
        let r=height(root.right)
        if(l-r>1||r-l>1) flag=false//这里最好还是用外部标记
        return Math.max(l+1,r+1)
    }
    height(pRoot)
   if(flag==false) return false
    return true
}

function IsBalanced_Solution(pRoot)
{
    // write code here
    if(pRoot==null) return true;
    //获取一个节点的树高
    function getTreeHight(node){
        if(node==null) return 0;
        let left = getTreeHight(node.left);
        let right = getTreeHight(node.right);
        return (left>right?left:right)+1;
    }
    //遍历二叉树
    let left = getTreeHight(pRoot.left)
	let right = getTreeHight(pRoot.right)
	if(Math.abs(left - right) > 1) return false
	return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)

}

function IsBalanced_Solution(pRoot)
{
    if (!pRoot) return true;
    return Math.abs(getMaxDepth(pRoot.left) - getMaxDepth(pRoot.right)) < 2;
}
function getMaxDepth(root) {
    if (!root) return 0;
    return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
}

function Depth(pRoot){
    if(!pRoot){
        return 0;
    }
    var left = Depth(pRoot.left);
    if(left == -1){
        return -1;
    }
    var right = Depth(pRoot.right);
    if(right == -1){
        return -1;
    }
    if(Math.abs(left - right) > 1){
        return -1;
    }
    return Math.max(left,right) + 1;
}
function IsBalanced_Solution(pRoot)
{
    // write code here
    return Depth(pRoot) != -1;
    
}

function IsBalanced_Solution(pRoot)
{
    // write code here
      if(pRoot == null) return true;
      function dfs(root) {
          if(root == null) return 0;
          return Math.max(dfs(root.left), dfs(root.right)) + 1;
      }
    let l = dfs(pRoot.left);
    let r = dfs(pRoot.right);
    return Math.abs(l - r) <= 1 && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
}

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

/**
 * 我的解题思路：
 * 1.直接复用上道题的逻辑，即先获取左右子树的深度，然后看它们差的绝对值是否小于等于1
 *
 * @param {*} pRoot
 */
function IsBalanced_Solution(pRoot)
{
    // write code here
    const fn = root => root ? Math.max(1 + fn(root.left), 1 + fn(root.right)) : 0;
    return pRoot ? Math.abs(fn(pRoot.left) - fn(pRoot.right)) <= 1 : true;
}

/**
 * 评论区TOP的解题思路：
 * 1.看起来跟我的思路好像差不多，实际上在对左右子树递归判断时处理不一样
 * 2.该思路是在发现某个子树不是平衡二叉树时，就直接原路返回到根节点并给出结果
 * 3.而我的思路是每次都会遍历完所有的子树
 *
 * @param {*} pRoot
 */
function topIsBalanced_Solution(pRoot)
{
    // write code here
    const fn = root => {
        if (!root) {
            return 0;
        }
        const left = fn(root.left);
        if (left === -1) {
            return -1;
        }
        const right = fn(root.right);
        if (right === -1) {
            return -1;
        }
        return Math.abs(left - right) > 1 ? -1 : 1 + Max(left, right);
    };
    return fn(pRoot) !== -1;
}

function TreeNode(x) {
    return {
        val:x,
        left:null,
        right:null
    }
}


function IsBalanced_Solution(pRoot)
{
    function TreeDepth(pRoot)
    {
        // write code here
        if(!pRoot) {
            return 0
        }
        const l = TreeDepth(pRoot.left)
        const r = TreeDepth(pRoot.right)
        const max = l > r ? l : r
        return max + 1
    }


    if(!pRoot) {
        return true
    }
    const l_d = TreeDepth(pRoot.left)
    const r_d = TreeDepth(pRoot.right)
    const dis = Math.abs(l_d-r_d)
    return dis <= 1 && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}

    function IsBalanced_Solution(pRoot) {
      return isBalanced(pRoot) != -1;
    }

    function isBalanced(node) {
      if (!node) {
        return 0;
      }
      const left = isBalanced(node.left);
      const right = isBalanced(node.right);
      if (left != -1 && right != -1) {
        const diff = left - right;
        if (diff <= 1 && diff >= -1) {
          return Math.max(left, right) + 1;
        }
      }
      return -1;
    }

function IsBalanced_Solution(pRoot)
{
    // write code here
    var res = findDeepAndIsBalanced(pRoot);
    function findDeepAndIsBalanced(node) {
        if (!node) return { isBalanced: true, depth: 0 };
        var leftRes = findDeepAndIsBalanced(node.left);
        var rightRes = findDeepAndIsBalanced(node.right);
        var isBalanced = Math.abs(leftRes.depth - rightRes.depth) <= 1;
        return { isBalanced, depth: Math.max( leftRes.depth, rightRes.depth ) + 1};
    }
    return res.isBalanced
}

子节点只需要遍历一次

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function IsBalanced_Solution(pRoot)
{
    // write code here
    //pRoot为空节点，则为平衡树，返回true
    if(pRoot == null){
        return true;
    }
    var leftDep = treeDep(pRoot.left);
    var rightDep = treeDep(pRoot.right);
    //leftDep和rightDep的差为0／1，则该树为平衡树，那么继续判断其左右／子树是否为平衡树。只有但子树也为平衡数时，才返回true
    if(Math.abs(leftDep-rightDep) <= 1){
        return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
    }
    else{return false;}
}
function treeDep(pRoot){
    if(pRoot == null){
        return 0;
    }
    var leftDep = treeDep(pRoot.left);
    var rightDep = treeDep(pRoot.right);
    return 1+(leftDep>rightDep?leftDep:rightDep);
}

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;
}

function IsBalanced_Solution(pRoot)
{
    return TreeDepth(pRoot)!=-1;
}
function TreeDepth(pRoot){
    if(pRoot==null) return 0;
    let leftLen=TreeDepth(pRoot.left);
    if(leftLen==-1)
        return -1;
    let rightLen=TreeDepth(pRoot.right);
    if(rightLen==-1)
        return -1;
    return Math.abs(leftLen-rightLen)>1?-1:Math.max(leftLen,rightLen)+1;
}