解法一:递归1
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null) return true;
return compare(root.left, root.right);
}
boolean compare(TreeNode p, TreeNode q){
if(p!=null&&!compare(p.left, p.right)) return false;
if(q!=null&&!compare(q.left, q.right)) return false;
//if(p.val!=q.val) return false;
return Math.abs(depth(p)-depth(q))<=1;
}
int depth(TreeNode root){
return root==null? 0:Math.max(depth(root.left), depth(root.right))+1;
}
}
解法二:递归2
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null) return true;
if (Math.abs(depth(root.left)-depth(root.right))>1) return false;
return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
}
int depth(TreeNode root){
return root==null? 0:Math.max(depth(root.left), depth(root.right))+1;
}
}
解法三:后序遍历
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return depth(root)!=-1;
}
int depth(TreeNode root){
if(root==null) return 0;
int l=depth(root.left);
if(l==-1) return -1;
int r=depth(root.right);
if(r==-1) return -1;
if(Math.abs(l-r)>1) return -1;
return Math.max(l,r)+1;
}
}