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

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

![这里写图片描述][70]

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));
        }
    }

[70]: /images/20220525/635bd246b3234fd69120becdd92a3792.png