958. Complete binary tree test

One 、 Title Description

Example 1：

 Input ：root = [1,2,3,4,5,6]
 Output ：true
 explain ： Every floor before the last floor is full （ namely , The node value is  {1}  and  {2,3}  The two layers ）, And all nodes in the last layer （{4,5,6}） As far left as possible .

Example 2：

 Input ：root = [1,2,3,4,5,null,7]
 Output ：false
 explain ： The value is  7  The node of is not as far to the left as possible .

Two 、 Problem solving

DFS

Current node N The value of the left child node of is 2N, The value of the right child node is 2N+1, Count the number of nodes during each traversal , And the maximum value of the node . If a complete binary tree is satisfied , Then the number of nodes and the maximum value are equal , Otherwise it's not equal

class Solution {
    
    // Maximum 
    int maxNum = 0;
    // Counting node 
    int cnt = 0;
    public boolean isCompleteTree(TreeNode root) {
    
        //DFS  The root node is N , The left child node 2*N  The right child node  2*N+1;
        if(root == null){
    
            return true;
        }
        dfs(root,1);
        return maxNum == cnt;
    }

    public void dfs(TreeNode root,int curNum){
    
        // Termination conditions 
        if(root == null){
    
            return;
        }
        maxNum = Math.max(maxNum,curNum);
        cnt++;
        dfs(root.left,2*curNum);
        dfs(root.right,2*curNum+1);
    }
}

BFS

Breadth first traversal . When there is a null Stop traversal on value , If there are nodes that have not been traversed at this time , It shows that the tree is not a complete binary tree .

class Solution {
    
    //  Breadth traversal binary tree , When there is a  null  Stop traversal on value , If there are nodes that have not been traversed at this time , It shows that the tree is not a complete binary tree .
    public boolean isCompleteTree(TreeNode root) {
    
        Deque<TreeNode> queue = new LinkedList<>();
        TreeNode cur;
        queue.add(root);
        
        while((cur = queue.poll()) != null){
    
            queue.add(cur.left);
            queue.add(cur.right);
        }
        // Judge whether the queue is empty 
        while(!queue.isEmpty()){
    
            if(queue.poll() != null){
    
                return false;
            }
        }
        return true;
    }
}