Judge whether the binary tree is a complete binary tree

1、 subject

Given the root node of a binary tree root, Judge whether this tree is a complete binary tree .

2、 analysis

A complete binary tree means that each layer is either full , If dissatisfaction is also full from left to right .

Classic practice

Traverse layer by layer , Follow several principles ：

• If a node has a right child , There is no left child , Then it must not be a complete binary tree ;
• When I first met a child who was not both right and left , The remaining traversal nodes must be leaf nodes , Otherwise, it is not a complete binary tree .

Recursive routine

1. The goal is ：X Whether a binary tree with a head is a complete binary tree ;

2. possibility ： classification —— Where is the last node on the last floor
   ① The last layer of nodes is full ： If the left tree is full , The right tree is also full , And the height of the left and right trees is the same , with X The binary tree with the head must be a complete binary tree .（ Zuo Shuman , The right tree is full , Left high = Right high ）
   ② The last layer node is not satisfied ：
       1) The last node is in the left tree , But the left tree is not full ： If the left tree is a complete binary tree , And the right tree is full , And the left tree is higher than the right tree 1, that X The binary tree with the head must be a complete binary tree .（ Left perfect , Right full , Left high = Right high + 1）
       2） The last node just makes the left tree full ： The left tree is full , The right tree is full , The height of the left tree is higher than that of the right tree 1, that X The binary tree with the head must be a complete binary tree .（ Zuo man , Right full , Left high = Right high + 1）
       3） The last node is on the right tree , But the right tree is not full ： The left tree is full , The right tree is a complete binary tree , And the height of the left and right trees is the same , that X The binary tree with the head must be a complete binary tree .（ Zuo man , Right perfect , Left high = Right high ）

3. To support this 4 A possibility , The information that needs to be collected from the left and right trees ：（1） Is it a full binary tree ;（2） Whether it is a complete binary tree ;（3） Height .

3、 Realization

C++ edition

/************************************************************************* > File Name: 041. Determine whether a binary tree is a complete binary tree .cpp > Author: Maureen > Mail: [email protected] > Created Time:  One  7/ 4 19:39:10 2022 ************************************************************************/

#include <iostream>
#include <ctime>
#include <queue>
using namespace std;

class TreeNode {
    
public:
    int value;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int data) : value(data) {
    }
};


// Method 1 ： Classic practice 
bool isCBT1(TreeNode *root) {
    
    if (root == nullptr) return true;

    queue<TreeNode*> _que;
    bool leaf = true; 
    TreeNode *l = nullptr;
    TreeNode *r = nullptr;
    _que.push(root);

    while (!_que.empty()) {
    
        root = que.front();
        que.pop();
        l = root->left;
        r = root->right;
        // Encountered an incomplete node and found that the current node is not a leaf node   or   There are right children but no left children 
        if (leaf && (l != nullptr || r != nullptr)) || (l == nullptr && r != nullptr) ) {
    
            return false;
        }

        if (l != nullptr) {
    
            _que.push(l);
        }

        if (r != nullptr) {
    
            _que.push(r);
        }

        if (l == nullptr || r == nullptr) {
     // Only one child , It's the situation of incomplete children 
            leaf = true;
        }
    }

    return true;
}



// Method 2 ： Recursive routine of binary tree 
class Info {
    
public:
    bool isFull;
    bool isCBT;
    int height;

    Info(bool full, bool cbt, int h) : 
        isFull(full), isCBT(cbt), height(h) {
    }
};


Info *process(TreeNode *x) {
    
    if (x == nullptr) {
    
        retur new Info(true, true, 0);
    }

    Info *leftInfo = process(x->left);
    Info *rightInfo = process(x->right);

    int height = max(leftInfo->height, rightInfo->height) + 1;


    bool isFull = leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height;

    bool isCBT = false;

    // possibility 1： Zuo man , Right full , Left high  =  Right high 
    if (leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height) {
    
        isCBT = true;
    } else if (leftInfo->isCBT && rightInfo->isFull && leftInfo->height == rightInfo->height + 1) {
     // possibility 2： Left perfect , Right full , Left high  =  Right high  + 1
        isCBT = true;
    } else if (leftInfo->isFull && rightInfo->isFull &&  leftInfo->height == rightInfo->height + 1) {
     // possibility 3： Zuo man , Right full , Left high  =  Right high  + 1
        isCBT = true;
    } else if (leftInfo->isFull && right->isCBT && leftInfo->height == rightInfo->height) {
     // possibility 4： Zuo man , Right perfect , Left high  =  Right high 
        isCBT = true;
    }

    return new Info(isFull, isCBT, height);
}

bool isCBT2(TreeNode *root) {
    
    return process(root)->isCBT;
}


//for test 
TreeNode *generate(int level, int maxl, int maxv) {
    
    if (level > maxl || (rand() % 100 / (double)101) < 0.5)
        return nullptr;

    TreeNode *root = new TreeNode(rand() % maxv);
    root->left = generate(level + 1, maxl, maxv);
    root->right = generate(level + 1, maxl, maxv);

    return root;
}

TreeNode *generateRandomBST(int level, int value) {
    
    return generate(1, level, value);
}

int main() {
    
    srand(time(0));
    int maxLevel = 4;
    int maxValue = 100;
    int testTimes = 1000001;

    cout << "Test begin:" << endl;
    for (int i = 0; i < testTimes; i++) {
    
        TreeNode *root = generateRandomBST(maxLevel, maxValue);
        if (isCBT1(root) != isCBT2(root)) {
    
            cout << "Failed!" << endl;
            return 0;
        }
        if (i && i % 1000 == 0) cout << i << " cases passed!" << endl;
    }

    cout << "Success!!" << endl;
    return 0;
}

Java edition

import java.util.LinkedList;

public class IsCBT {
    

	public static class Node {
    
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
    
			this.value = data;
		}
	}
	
    // Classic practice 
	public static boolean isCBT1(Node head) {
    
		if (head == null) {
    
			return true;
		}
		LinkedList<Node> queue = new LinkedList<>();
		//  Have you ever met a node with incomplete left and right children 
		boolean leaf = false;
		Node l = null;
		Node r = null;
		queue.add(head);
		while (!queue.isEmpty()) {
    
			head = queue.poll();
			l = head.left;
			r = head.right;
			if (
			//  If you encounter incomplete nodes , It is also found that the current node is not a leaf node 
			    (leaf && (l != null || r != null)) 
			    || 
			    (l == null && r != null) // Whether there is right or left 

			) {
    
				return false;
			}
			if (l != null) {
    
				queue.add(l);
			}
			if (r != null) {
    
				queue.add(r);
			}
			if (l == null || r == null) {
     // If there is only one child or no child , It's the case of incomplete children 
				leaf = true;
			}
		}
		return true;
	}

    // Recursive routine 
	public static boolean isCBT2(Node head) {
    
        return process(head).isCBT;
    }

    public static class Info {
    
        public boolean isFull; // Is it full 
        public boolean isCBT;//  Is it a complete binary tree 
        public int height; // Height 
        public Info(boolean full, boolean cbt, int h) {
    
            isFull = full;
            isCBT = cbt;
            height = h;
        }
    }

    public static Info process(Node x) {
    
        if (x == null) {
     // Empty tree settings 
            return new Info(true, true, 0);
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        // The trees on both sides are full , And highly consistent , It's full of binary trees 
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;

        boolean isCBT = false;
        // possibility 1： The trees on both sides are full , And highly consistent 
        if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {
    
            isCBT = true;
        }
        // possibility 2： The left tree is completely , The right tree is full , The left tree is taller than the right 1
        else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
    
            isCBT = true;
        }
        // possibility 3： The left tree is full , The right tree is full , The left tree is taller than the right 1
        else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
    
            isCBT = true;
        }
        // possibility 4： The left tree is full , The right number is complete , The height of the left and right trees is the same 
        else if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
    
            isCBT = true;
        }
        return new Info(isFull, isCBT, height);
    }
	

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
    
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
    
		if (level > maxLevel || Math.random() < 0.5) {
    
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
    
		int maxLevel = 5;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
    
			Node head = generateRandomBST(maxLevel, maxValue);
			if (isCBT1(head) != isCBT2(head)) {
    
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}
}