判断二叉树是否为完全二叉树

1、题目

给定一棵二叉树的根节点root，判断这棵树是否为完全二叉树。

2、分析

完全二叉树就是每一层要么是满的，如果不满也是从左到右依次变满。

经典做法

按层遍历，遵循几个原则：

• 如果某个节点有右孩子，没有左孩子，则它一定不是完全二叉树；
• 当第一次遇到左右孩子不双全的时候，剩下遍历的节点必须是叶节点，否则不是完全二叉树。

递归套路

1. 目标：X 为头的二叉树是否为完全二叉树；

2. 可能性：分类——最后一层的最后一个节点到哪儿了
   ① 最后一层节点是满的：如果左树是满的，右树也是满的，且左右树高度一致，则以 X 为头的这棵二叉树一定是完全二叉树。（左树满，右树满，左高 = 右高）
   ②最后一层节点不满：
       1) 最后一个节点在左树，但是左树没满：如果左树是完全二叉树，且右树是满的，且左树比右树高度大1，那么 X 为头的这棵二叉树一定是完全二叉树。（左完全，右满，左高 = 右高 + 1）
       2）最后一个节点刚好使得左树满：左树是满的，右树是满的，左树高度比右树高度大1，那么 X 为头的这棵二叉树一定是完全二叉树。（左满，右满，左高 = 右高+ 1）
       3）最后一个节点在右树上，但是右树没满：左树是满的，右树是完全二叉树，且左右树高度一致，那么 X 为头的这棵二叉树一定是完全二叉树。（左满，右完全，左高 = 右高）

3. 为了支持这 4 种可能性，需要向左右树收集的信息：（1）是否是满二叉树；（2）是否是完全二叉树；（3）高度。

3、实现

C++ 版

/************************************************************************* > File Name: 041.判断二叉树是否为完全二叉树.cpp > Author: Maureen > Mail: [email protected] > Created Time: 一 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) {
    }
};


//方法一：经典做法
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;
        //遇到了不双全的节点且发现当前节点不是叶节点 或 有右孩子无左孩子
        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) {
     //只有一个孩子，就是孩子不双全的情况
            leaf = true;
        }
    }

    return true;
}



//方法二：二叉树的递归套路
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;

    //可能性1：左满，右满，左高 = 右高
    if (leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height) {
    
        isCBT = true;
    } else if (leftInfo->isCBT && rightInfo->isFull && leftInfo->height == rightInfo->height + 1) {
     //可能性2：左完全，右满，左高 = 右高 + 1
        isCBT = true;
    } else if (leftInfo->isFull && rightInfo->isFull &&  leftInfo->height == rightInfo->height + 1) {
     //可能性3：左满，右满，左高 = 右高 + 1
        isCBT = true;
    } else if (leftInfo->isFull && right->isCBT && leftInfo->height == rightInfo->height) {
     //可能性4：左满，右完全，左高 = 右高
        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 版

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;
		}
	}
	
    //经典做法
	public static boolean isCBT1(Node head) {
    
		if (head == null) {
    
			return true;
		}
		LinkedList<Node> queue = new LinkedList<>();
		// 是否遇到过左右两个孩子不双全的节点
		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 (
			// 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
			    (leaf && (l != null || r != null)) 
			    || 
			    (l == null && r != null) //有右无左的情况

			) {
    
				return false;
			}
			if (l != null) {
    
				queue.add(l);
			}
			if (r != null) {
    
				queue.add(r);
			}
			if (l == null || r == null) {
     //如果只存在一个孩子或没有孩子，就是遇到了孩子不双全的情况
				leaf = true;
			}
		}
		return true;
	}

    //递归套路的做法
	public static boolean isCBT2(Node head) {
    
        return process(head).isCBT;
    }

    public static class Info {
    
        public boolean isFull; //是否满的
        public boolean isCBT;// 是否完全二叉树
        public int height; //高度
        public Info(boolean full, boolean cbt, int h) {
    
            isFull = full;
            isCBT = cbt;
            height = h;
        }
    }

    public static Info process(Node x) {
    
        if (x == null) {
     //空树的设置
            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;

        //左右树都是满的，且高度一致，就是满二叉树
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;

        boolean isCBT = false;
        //可能性1：左右树都是满的，且高度一致
        if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {
    
            isCBT = true;
        }
        //可能性2：左树是完全，右树是满的，左树比右树高1
        else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
    
            isCBT = true;
        }
        //可能性3：左树是满的，右树是满的，左树比右树高1
        else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
    
            isCBT = true;
        }
        //可能性4：左树是满的，右数是完全，左右树高度一致
        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!");
	}
}