首页 > 代码库 > 【复】判断树的平衡,

【复】判断树的平衡,

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