[LeetCode]Check Completeness of a Binary Tree

题目链接

这道题需要我们check给定的binary tree是不是complete binary tree，我们需要verify以下几点：

1. 是不是只有最后一层是不满的，换言之，除了最后一层外，其他的层数h(从零开始)的节点数量应该为2^h
2. 如果最后一层是不满的话，是不是所有节点都尽量向左靠拢

为了verify这两点，我们需要使用层序遍历，在check每一层的时候验证以上两点。假设Tree的size为N，时间复杂度O(N)，空间复杂度O(N)，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isCompleteTree(TreeNode* root) {
	if(!root)return true;
	queue<TreeNode*> q;
	int depth = 0;
	q.push(root);
	while(q.size())
	{
	int len = q.size();
	bool hasNull = false;
	if((1 << depth) != len)
	{
	//verify if it is the last laryer
	for(int i = 0; i < len; ++i)
	{
	auto node = q.front();
	q.pop();
	if(node->left || node->right)return false;
	}
	}
	else
	{
	//verify all nodes in next level are posed as left as possible
	for(int i = 0; i < len; ++i)
	{
	auto node = q.front();
	q.pop();
	if(node->left){ if(hasNull)return false; q.push(node->left); }
	else hasNull = true;
	if(node->right){ if(hasNull)return false; q.push(node->right); }
	else hasNull = true;
	}
	}
	++depth;
	}
	return true;
	}
	};

view raw Check Completeness of a Binary Tree_2.cpp hosted with ❤ by GitHub

此外，我们可以给所有的节点标号。根节点为0，从上到下，从左到右递增，其他节点按照应该出现的位置标记一个整数。如果给定的树是complete binary tree，那么所有的节点的编号应当是从0到N-1连续的数，我们只需要check最后一个数是不是等于N - 1即可。时间复杂度O(N)，空间复杂度O(N)，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isCompleteTree(TreeNode* root) {
	if(!root)return true;
	vector<pair<TreeNode*, int>> nodes;
	nodes.emplace_back(root, 0);
	int i = 0;
	while(i < nodes.size())
	{
	auto node = nodes[i].first;
	int label = nodes[i].second;
	if(node->left)nodes.emplace_back(node->left, 2 * label + 1);
	if(node->right)nodes.emplace_back(node->right, 2 * label + 2);
	++i;
	}
	return nodes.back().second + 1 == nodes.size();
	}
	};

view raw Check Completeness of a Binary Tree.cpp hosted with ❤ by GitHub