Judge whether the binary tree is full binary tree

1、 subject

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

2、 analysis

Full binary tree ： If the height of the tree is $h$, Then the number of nodes must be $2^h-1$.

So according to the recursion routine of binary tree ： hypothesis X Is the tree of the root node , The left and right subtrees collect two pieces of information ： Height $h$ and Number of nodes $n$, Judge whether the condition of full binary tree is satisfied .

in addition , If the left tree is full of binary trees , The right tree is full of binary trees , And the height of the left and right trees is the same , Then the whole tree is full of binary trees .

therefore , You can also use the recursive routine of binary trees , Get information from the left and right trees ：（1） Whether it is a full binary tree （2） Height

3、 Realization

C++ edition

/************************************************************************* > File Name: 036. Judge whether the binary tree is full binary tree .cpp > Author: Maureen > Mail: [email protected] > Created Time:  5、 ... and  7/ 1 16:37:02 2022 ************************************************************************/

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

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

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


// Method 1： Collect the height and number of nodes of the whole tree  
// Only full binary trees satisfy ：2^h - 1 == n
class Info1 {
    
public:
    int height;// Height 
    int nodeCnt;// Number of nodes 

    Info1(int h, int c) : height(h), nodeCnt(c) {
    }
};


Info1 *process1(TreeNode *x) {
    
    if (x == nullptr) {
    
        return new Info1(0, 0);
    }

    Info1 *leftInfo = process1(x->left);
    Info1 *rightInfo = process1(x->right);

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

    return new Info1(height, nodeCnt);
}

bool isFullBT1(TreeNode *root) {
    
    if (root == nullptr) return true;
    
    Info1 *info = process1(root);

    return (1 << info->height) - 1 == info->nodeCnt;
}


// Method 2:  collect   Whether the subtree is full of binary tree   and   Subtree height  
// Zuo Shuman  &&  The right tree is full  &&  The height of the left tree is the same as that of the right tree , Then the whole tree is full 
class Info2 {
    
public:
    bool isFull;
    int height;

    Info2(bool isfull, int h) : isFull(isfull), height(h) {
    }
};

Info2 *process2(TreeNode *x) {
    
    if (x == nullptr) {
    
        return new Info2(true, 0);
    }

    Info2 *leftInfo = process2(x->left);
    Info2 *rightInfo = process2(x->right);

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

    return new Info2(isFull, height);
}


bool isFullBT2(TreeNode *root) {
    
    return process2(root)->isFull;
}


//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 level = 5;
    int value = 100;
    int testTimes = 1000001;

    cout << "Test begin:" << endl;
    for (int i = 0; i < testTimes; i++) {
    
        TreeNode *root = generateRandomBST(level, value);
        if (isFullBT1(root) != isFullBT2(root)) {
    
            cout << "Failed!" << endl;
            return 0;
        }
    }
    cout << "Success!" << endl;
    return 0;
}

Java edition

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

		public Node(int data) {
    
			this.value = data;
		}
	}    

	//  The first method 
	//  Collect the height of the whole tree h, And the number of nodes n
	//  Only full binary trees satisfy  : 2 ^ h - 1 == n
	public static boolean isFull1(Node head) {
    
		if (head == null) {
    
			return true;
		}
		Info1 all = process1(head);
		return (1 << all.height) - 1 == all.nodes;
	}

	public static class Info1 {
    
		public int height; // Height 
		public int nodes; // Number of nodes 

		public Info1(int h, int n) {
    
			height = h;
			nodes = n;
		}
	}

	public static Info1 process1(Node head) {
    
		if (head == null) {
    
			return new Info1(0, 0);
		}
		Info1 leftInfo = process1(head.left);
		Info1 rightInfo = process1(head.right);
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		int nodes = leftInfo.nodes + rightInfo.nodes + 1;
		return new Info1(height, nodes);
	}

	//  The second method 
	//  Collect whether the subtree is a full binary tree 
	//  Collect the height of the subtree 
	//  Zuo Shuman  &&  The right tree is full  &&  The height of the left and right trees is the same  ->  The whole tree is full 
	public static boolean isFull2(Node head) {
    
		if (head == null) {
    
			return true;
		}
		return process2(head).isFull;
	}

	public static class Info2 {
    
		public boolean isFull; 
		public int height;

		public Info2(boolean f, int h) {
    
			isFull = f;
			height = h;
		}
	}

	public static Info2 process2(Node h) {
    
		if (h == null) {
    
			return new Info2(true, 0);
		}
		Info2 leftInfo = process2(h.left);
		Info2 rightInfo = process2(h.right);
		boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		return new Info2(isFull, 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;
		System.out.println(" Beginning of the test ");
		for (int i = 0; i < testTimes; i++) {
    
			Node head = generateRandomBST(maxLevel, maxValue);
			if (isFull1(head) != isFull2(head)) {
    
				System.out.println(" Something went wrong !");
			}
		}
		System.out.println(" End of test ");
	}    
}