判断是不是平衡二叉树

//pos-order遍历，使用辅助数组depth来保存每一步遍历的深度，同时返回该节点是否是平衡的
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return isBalance(root,new int[1]);
    }
    public boolean isBalance(TreeNode root,int []depth){
        if(root==null){
            depth[0]=0;
            return true;
        }
        boolean left=isBalance(root.left,depth);
        int leftdepth=depth[0];
        boolean right=isBalance(root.right,depth);
        int rightdepth=depth[0];
        depth[0]=Math.max(leftdepth+1,rightdepth+1);
        if(left&&right&&Math.abs(leftdepth-rightdepth)<=1)return true;
        return false;
    }
}

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(helper(pRoot) < 0) return false;
        return true;
    }
private:
    int helper(TreeNode* node){
        if(node == NULL) return 0;
		int ld = helper(node->left);
        if(ld == -1) return -1;    //若左边已经不是平衡二叉树了，那就直接返回，没必要搜索右边了 
        int rd = helper(node->right);     
		if(rd == -1 || abs(ld-rd) > 1) return -1; //-1代表：不是平衡二叉树
        return max(ld, rd)+1;
    }
};

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

# -*- coding:utf-8 -*-
"""
深度优先遍历二叉树
    某个结点的子树不平衡或者自己不平衡则返回-1
    其他情况返回树深（从叶向上数）
    最后调用DFS函数查看返回值是否为-1，不为-1，则返回True,否则返回False
"""
class Solution:
    def IsBalanced_Solution(self, pRoot):
        #方法1： 深度优先遍历结点，结点不平衡则返回-1
        def dfs(root):
            #这是给叶子结点的
            if root is None:return 0 
            l_depth  = dfs(root.left)
            r_depth = dfs(root.right)
            #左子树不平衡，或右子树不平衡，或当前树结点不平衡 直接返回-1
            if l_depth == -1 or r_depth == -1 or abs(l_depth - r_depth)>1:
                return -1
            return 1 + max(l_depth, r_depth) # 返回当前树的深度
        
        if not pRoot:return True#鲁棒性代码
        return dfs(pRoot) != -1 # 成立说明平衡

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