Yyds dry inventory solution sword finger offer: judge whether it is a balanced binary tree

1. sketch ：

describe

Enter a node number of n Binary tree , Determine whether the binary tree is a balanced binary tree . ad locum , We just need to think about the balance , It is not necessary to consider whether it is a sort binary tree or a balanced binary tree （Balanced Binary Tree）, It has the following properties ： It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, And both the left and right subtrees are a balanced binary tree .

Sample explanation ： The sample binary tree is shown in the figure below , For a balanced binary tree

notes ： We agree that an empty tree is a balanced binary tree .

Data range ：, The nodes on the tree val It's worth it   requirement ： Spatial complexity , Time complexity  

Input description ：

Enter the root node of a binary tree

Return value description ：

Output a Boolean value

Example 1

Input ：

Log in and copy

      
      

       
       {1,2,3,4,5,6,7}
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       true
      
      
      
      

       
       
1.
      
      

Example 2

Input ：

Log in and copy

      
      

       
       {}
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       true
      
      
      
      

       
       
1.
      
      

2. Code implementation ：

Log in and copy

      
      

       
       public class Solution {
       
       
    public boolean IsBalanced_Solution(TreeNode root) {
       
       
         if(root == null){
       
       
            return true;
       
       
        }
       
       
        int left = deep(root.left);
       
       
        int right = deep(root.right);
       
       
        int v = Math.abs(left - right);
       
       
        if(v > 1){
       
       
            return false;
       
       
        }
       
       
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
       
       
    }
       
       
    
       
       
     private int deep(TreeNode root) {
       
       
        if(root == null){
       
       
            return 0;
       
       
        }
       
       
        return Math.max(deep(root.left), deep(root.right)) + 1;
       
       
     }
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.