Niuke topic -- judge whether it is a complete binary tree or a balanced binary tree

---

subject 1—— Determine whether it is a complete binary tree

Given a binary tree , Determine if it is a complete binary tree .

The definition of a complete binary tree ： If the depth of the binary tree is h, In addition to h Out of layer , The number of nodes in other layers reaches the maximum , The first h All leaf nodes of layer are continuously concentrated on the leftmost , This is a completely binary tree .
The following example figure 1、2 It's a perfect binary tree , And the sample diagram 3 No .

Their thinking

In a complete binary tree, leaf nodes can only appear in the lowest and lower levels , And the lowest leaf nodes are concentrated in the left part of the tree .
The specific methods are as follows ：

• First, judge that the empty tree must be a complete binary tree ;
• Initialize a queue auxiliary level traversal , And join the root node into the team ;
• Gradually visit the first node of the team , If a node is empty , Then mark , Represents the lowest level of a complete binary tree , If there are subsequent nodes that are not empty , It does not conform to the properties of a complete binary tree ;
• otherwise , Continue to add the left and right child nodes to the queue , Waiting for access .

Code implementation

public class Solution {
    
    public boolean isCompleteTree (TreeNode root) {
    
       if(root == null) return true;
        boolean complete = false;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
    
            // Gradually visit the first element of the team 
            TreeNode cur = q.poll();
            // If the team leader element is empty , Indicates that the empty node is encountered for the first time , marked 
            if(cur == null){
    
                complete = true;
                continue;
            }
            // After the empty node , And nodes , Does not conform to the nature of binary tree 
            if(complete) return false;
            // None of the above is satisfied , Queue the left and right child nodes of the current node , Waiting for access 
            q.add(cur.left);
            q.add(cur.right);
        }
        return true;
    }
}

subject 2—— Determine whether it is a balanced binary tree

Given the number of nodes of a tree is n Two fork tree , Determine whether the binary tree is a balanced binary tree .

Properties of balanced binary trees ： It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, And the left and right subtrees are both balanced binary trees .
The following example is a balanced binary tree .

Their thinking

According to the definition , If we can find the height of the tree , Then, the absolute value of the height difference between the left and right subtrees is less than or equal to 1, We can judge whether the tree with each node as the root meets the definition .
The specific methods are as follows ：

• First, find the height of the subtree around the root node , And judge whether the absolute value of the height difference does not exceed 1;
• Recursively judge whether the left subtree and the right subtree are balanced binary trees ;
• When the three conditions are met at the same time , Balanced binary tree .

Code implementation

public class Solution {
    
    // Solve the height of the tree 
    public int getHeight(TreeNode node){
    
        int height = 0;
        if(node == null) return height;
        int l = getHeight(node.left);
        int r = getHeight(node.right);
        return Math.max(l,r)+1;
    }
    public boolean IsBalanced_Solution(TreeNode root) {
    
        if(root == null) return true;
        int l = getHeight(root.left);
        int r = getHeight(root.right);
        // The difference in height is greater than 1, It's not an equilibrium binary tree 
        if(Math.abs(l-r)>1) return false;
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
}