N39_判断该二叉树是否是平衡二叉树。

矫情吗；* 2023-08-17 17:36 132阅读 0赞

## 题目描述 ##

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

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