题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
package new_offer;
/**
* 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
* @author Sonya
*思路：
*1、借鉴上题 求树的深度。但是效率不高 需要重复遍历结点多次。
*2、后续遍历，记录每个depth 只需要遍历一次。
*/
public class N39_IsBalanced_Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null) return true;
int left=TreeDepth(root.left);
int right=TreeDepth(root.right);
int val=left-right;
if(Math.abs(val)>1)return false;
return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
}
public int TreeDepth(TreeNode root) {
if(root==null)return 0;
int left=TreeDepth(root.left);
int right=TreeDepth(root.right);
if(left>right) return left+1;
else return right+1;
}
public boolean IsBalanced_Solution2(TreeNode root) {
int dep = 0;
return IsBalanced(root, dep);
}
public boolean IsBalanced(TreeNode root,int depth) {
if(root==null) {depth=0;return true;}
int left,right;
left=right=0;
if(IsBalanced(root.left,left)&&IsBalanced(root.right,right)) {
int val=left-right;
if(Math.abs(val)>1)return false;
depth=(left>right?left:right)+1;
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
转载于:https://www.cnblogs.com/kexiblog/p/11175684.html
