Binary tree - 110. Balanced binary tree

1 Title Description

Given a binary tree , Determine if it's a highly balanced binary tree .

In this question , A height balanced binary tree is defined as ：

Every node of a binary tree The absolute value of the height difference between the left and right subtrees is not more than 1 .

2 Title Example

Example 3：

Input ：root = []
Output ：true

3 Topic tips

The number of nodes in the tree is in the range [0, 5000] Inside
-104 <= Node.val <= 104

4 Ideas

The definition of balanced binary tree in this problem is ： The absolute value of the height difference between the left and right subtrees of each node of the binary tree does not exceed 11, Then the binary tree is a balanced binary tree . According to the definition , A binary tree is a balanced binary tree , If and only if all its subtrees are balanced binary trees , Therefore, we can use the recursive method to judge whether the binary tree is a balanced binary tree , The order of recursion can be top-down or bottom-up .

With the function of calculating the height of nodes , We can judge whether the binary tree is balanced . The specific method is similar to the preorder traversal of binary tree , That is, for the node currently traversed , First, calculate the height of the left and right subtrees , If the height difference between the left and right subtrees does not exceed 11, Then recursively traverse the left and right child nodes , And judge whether the left subtree and the right subtree are balanced . This is a top-down recursive process .

Complexity analysis
Time complexity :o(n²), among n Is the number of nodes in the binary tree . In the worst case , A binary tree is a full binary tree , You need to traverse all nodes in the binary tree , The time complexity is O(n).
For the node p, If its height is d, be height§ At most d Time （ That is, when traversing each of its ancestor nodes ). For the average case , The height of a tree h Satisfy O(h)= O(logn), because d<h, So the total time complexity is O(n logn). For the worst case , Binary trees form a chain structure , The height is O(n), At this time, the total time complexity is o(n²).
Spatial complexity :O(n), among n Is the number of nodes in the binary tree . The space complexity mainly depends on the number of layers of recursive calls , The number of layers of recursive calls will not exceed n.

5 My answer

class Solution {
    
    public boolean isBalanced(TreeNode root) {
    
        if (root == null) {
    
            return true;
        } else {
    
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        } else {
    
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}