【复】判断树的平衡,

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int d1=depth(root.right);
        int d2=depth(root.left);
        if(Math.abs(d1-d2)>1) return false;
        else  return isBalanced(root.left)&&isBalanced(root.right);
         
        
        
        
    }
    
    public int depth(TreeNode node)
    {
        if(node==null) return 0;
        int d1=depth(node.right);
        int d2=depth(node.left);
        
        int max=d1>d2?d1:d2;
        return  max+1;
        
    }
    
}
View Code

2.求高度的时候在不平衡的时候返回-1就ok了,不用求高度,但是效率好像没啥变化

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private boolean ans=true;
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        if(depth(root)==-1) return false;
        return true;
        
       
        
        
        
    }
    
    public int depth(TreeNode node)
    {
        if(node==null) return 0;
        int d1=depth(node.right);
        int d2=depth(node.left);
        if(d1==-1||d2==-1) return -1;
        if(Math.abs(d1-d2)>1) return -1;
        
    
        
        
        return  Math.max(d1,d2)+1;
        
    }
    
}
原文地址:https://www.cnblogs.com/hansongjiang/p/3856549.html