判断一棵二叉树是否是平衡二叉树-蒲公英云

判断一棵二叉树是否是平衡二叉树

た入场券 2022-05-25 12:44 381阅读 0赞

这里写图片描述

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    //解法一:递归的解法
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
        return Math.abs(TreeDepth(root.left)-TreeDepth(root.right))>1&&IsBalanced_Solution(root.left)
               &&IsBalanced_Solution(root.right)?false:true;
    }
    //求二叉树的深度
    public int TreeDepth(TreeNode node){
         if(node==null)
             return 0;
         return Math.max(TreeDepth(node.left)+1,TreeDepth(node.right)+1);
    }
   //解法二:优化后的解法
    public boolean IsBalanced_Solution2(TreeNode root) {
           return TreeDepth2(root)!=-1;
    }
    public  int TreeDepth2(TreeNode node){
          if(node==null) return 0;
          int left=TreeDepth2(node.left); //从树的最底层进行比较
          if(left==-1) return -1;
          int right=TreeDepth2(node.right);
          if(right==-1) return -1;
          return Math.abs(left-right)>1?-1:1+Math.max(left,right);
    }
    public static void main(String[]args){
        //System.out.println("Hello");
        TreeNode root=new TreeNode(1);
         root.left=new TreeNode(2);
         root.right=new TreeNode(3);
         root.left.left=new TreeNode(4);
         root.left.right=new TreeNode(5);
         //root.left.left.left=new TreeNode(6);
         // root.left.left.right=new TreeNode(7);
         Solution s=new Solution();
         System.out.println(s.IsBalanced_Solution2(root));
    }
}