判断是不是平衡二叉树

class Solution {
public:
    int getDepth(TreeNode* t){
        if(t==NULL)
            return 0;
        int leftDepth=getDepth(t->left);
        int rightDepth=getDepth(t->right);
        return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
		if(pRoot==NULL)
            return true;
        int leftDepth=getDepth(pRoot->left);
        int rightDepth=getDepth(pRoot->right);
        int diffDepth=leftDepth-rightDepth;
        if(diffDepth<-1 || diffDepth>1){
            return false;
        }else{
            return (IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right));
        }
    }
};

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
         if(!pRoot)
               return true;
         if(!pRoot->left&&!pRoot->right)
               return true;
         int l = getDepth(pRoot->left);
         int r = getDepth(pRoot->right);
         if(l-r>1||l-r<-1)
             return false;
        return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
        
    }
    int getDepth(TreeNode *pRoot)
    {
        if(!pRoot)
              return 0;
        if(!pRoot->left&&!pRoot->right)
              return 1;
        int l = getDepth(pRoot->left);
        int r = getDepth(pRoot->right);
        
        return l>r?l+1:r+1;
    }
};

public classSolution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) {
            return true;
        }
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
            IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
     
    private int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }
    
    private int getDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        if (left == -1) return -1;
        int right = getDepth(root.right);
        if (right == -1) return -1;
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

#include <stdbool.h>

int dfs(struct TreeNode* root, bool* ans) {
  if (!root) return 0;
  const int lh = dfs(root->left,  ans); // lh == left subtree height
  const int rh = dfs(root->right, ans); // rh == right subtree height
  if (abs(lh - rh) > 1) *ans = false;
  return 1 + fmax(lh, rh);
}

bool IsBalanced_Solution(struct TreeNode* pRoot ) {
  if (!pRoot) return true;
  bool ans = true;
  dfs(pRoot, &ans);
  return ans;
}

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
            if (root == null) {
            return true;
        }
        if(Math.abs(getDeep(root.left, 0) - getDeep(root.right, 0)) > 1) {
            return false;
        }
        IsBalanced_Solution(root.right);
        IsBalanced_Solution(root.left);
        return true;
    }    
    public int getDeep(TreeNode node, int count) {
        if (node == null) {
            return count;
        }
        return Math.max(getDeep(node.left, count + 1), getDeep(node.right, count + 1));
    }
}

import java.util.Stack;
import java.util.ArrayList;

public class Solution {
    public boolean res = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        TreeNode cur = root;
        bs(cur);
        return res;
        //return Math.abs(bs(cur.left) - bs(cur.right)) <= 1 ? true : false;
    }
    
    public int bs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = bs(node.left);
        int right = bs(node.right);
        if (Math.abs(left - right) > 1) {
            res = false;
        }
        return right > left ? right + 1 : left + 1;
    }
}

class Solution:
    def IsBalanced_Solution(self, pRoot):
        return self.solution(pRoot)
    
    def getDepth(self,tree):
        if tree is None: return 0
        if not (tree.left or tree.right):return 1
        return 1 + max(self.getDepth(tree.left),self.getDepth(tree.right))

    def solution(self,tree):
        if tree is None:return True
        
        left = self.getDepth(tree.left)
        right = self.getDepth(tree.right)
        if abs(left-right) > 1:return False
        
        return  self.solution(tree.left) and  self.solution(tree.right)

//后序遍历，因为根是最后遍历到的，所以前面的数据已经有了
class Solution {
public:
    bool m_flag=true;
    bool IsBalanced_Solution(TreeNode* pRoot) {
		vis(pRoot);
        return m_flag;
    }
    
    int vis(TreeNode *p){
         if(!p)return 0;
         int l=vis(p->left);
         int r=vis(p->right);
         if(l-r>1 || r-l>1)m_flag=false;        
         return max(1+l,1+r);
    }
};

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
	    try{
            height(pRoot);
            return true;
        }catch(string * e){
            return false;
        }
    }
    
    int height(TreeNode * root){
        if(!root)return 0;
		int left = 1 + height(root->left);
        int right = 1 + height(root->right);
		if(abs(left - right)>1)throw new string();
        return max(left,right);
    }
};

    int balance(TreeNode* root){
        if(!root)
            return 0;
        int left=balance(root->left);  //左子树高度  
        if(left==-1)     //如果左子树返回-1，说明左子树不平衡，返回-1提前终止
            return -1;
        int right=balance(root->right);  //右子树高度 
        if(right==-1)  //如果右子树返回-1，说明右子树不平衡，返回-1提前终止
            return -1;
        if(left-right>1 || left-right<-1)  //左右子树高度差超过1，返回-1表示不平衡
            return -1;
        return max(left,right)+1;  //执行到这一步说明左右子树平衡，返回子树高度
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return balance(pRoot) != -1;
    }

public class Solution {
    //判断根节点左右子树的深度，高度差超过1，则不平衡
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root==null) {
			return true;
		}
		int left = getTreeDepth(root.left);
		int right = getTreeDepth(root.right);
		return Math.abs(left-right)>1?false:true;
    }
    //求取节点的深度
	public static int getTreeDepth(TreeNode root) {
		if (root==null) {
			return 0;
		}
		int leftDepth = 1+getTreeDepth(root.left);
		int rightDepth = 1+getTreeDepth(root.right);
		return leftDepth>rightDepth?leftDepth:rightDepth;
	}
}

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
      
        int left=depth(root.left);
        int right=depth(root.right);
        if(Math.abs(left-right)>1)
            return false;
        
        boolean booleft=IsBalanced_Solution(root.left);
        boolean booright=IsBalanced_Solution(root.right);
        return booleft&&booright;
    }

    public int depth(TreeNode root){
        if(root==null)
            return 0;
        int left=depth(root.left);
        int right=depth(root.right);
        return (left>right)?(left+1):(right+1);
    }
}

    # 递归判断
    # 以某节点为根的子树平衡需要：该节点平衡&左子树平衡&右子树平衡
    # 判断平衡需要获得左右子树的高度
    # 该函数在某子树平衡时返回其高度，不平衡时返回False
    # 利用and逻辑的短路性质剪枝，可以提前结束
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:  # 空树的高度设为1（避免高度为0和不平衡的False产生歧义）
            return 1
        l = self.IsBalanced_Solution(pRoot.left)
        if not l:  # 如果左子树不平衡
            return False
        r = self.IsBalanced_Solution(pRoot.right)
        if not r:  # 如果右子树不平衡
            return False
        if abs(l-r) < 2:  # 如果左右子树和本节点均平衡，返回该子树高度
            return 1 + max(l,r)
        else:  # 如果本节点不平衡
            return False

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) return true;
        return recur(root) != -1;
    }
    public int recur(TreeNode root) {
        if(root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

def check(node):
    if node is None:
        return 0, True
    
    # 不是叶节点
    if node.left&nbs***bsp;node.right:
        h1, res1 = check(node.left)
        h2, res2 = check(node.right)
        height = max(h1, h2) + 1
        if abs(h1-h2)<=1 and res1 and res2:
            res = True
        else:
            res = False
        return height, res
    # 叶节点
    else:    
        return 1, True

    
class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        return check(pRoot)[1]

import java.lang.*;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null) return true;
        return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right) ? true : false;
    }
    public int maxDepth (TreeNode root) {
        // write code here
        if(root==null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

function IsBalanced_Solution(pRoot)
{
    if(pRoot === null){
        return true;
    }
//     左右子树的高度绝对值相差大于1，则不是平衡二叉树
    if(Math.abs(depth(pRoot.left) - depth(pRoot.right)) > 1) return false;
//     进一步判断左右子树是否为平衡二叉树
    return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
}

// 求二叉树的深度
function depth(node){
    if(node === null){
        return 0;
    }
    let left = depth(node.left);
    let right = depth(node.right);
    return Math.max(left,right) + 1;
}