leetcode 958. 二叉树的完全性检验

大耗子 2021年02月19日 13次浏览

题目:958. 二叉树的完全性检验

958. 二叉树的完全性检验

难度中等

给定一个二叉树,确定它是否是一个完全二叉树

百度百科中对完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)

示例 1:

img

输入:[1,2,3,4,5,6]
输出:true
解释:最后一层前的每一层都是满的(即,结点值为 {1} 和 {2,3} 的两层),且最后一层中的所有结点({4,5,6})都尽可能地向左。

示例 2:

img

输入:[1,2,3,4,5,null,7]
输出:false
解释:值为 7 的结点没有尽可能靠向左侧。

提示:

  1. 树中将会有 1 到 100 个结点。

解题思路

第一个节点从1开始,如果父节点是n,那么左子节点的位置就是2*n,右子节点的位置就算2*n+1。 由于完全二叉树,节点按层次打印下来,顺序一定不会有空缺,那么可以根据这个规律,写出对应的代码。

  1. 将节点的值设置为层次遍历的顺序位置。相当于数组转换成树那种方法的下标+1。
  2. 将节点依次入容器,如果容器的最后一个节点的值与下标+1位置不相等,说明中间一定出现了空缺。那么这一定不是完全二叉树。
  3. 重复步骤2即可。

代码

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	bool isCompleteTree(TreeNode* root) {
		if (!root) return false;
		vector<TreeNode *> nodes;
		root->val = 1;
		nodes.push_back(root);
		int i = 0;
		while (nodes.size() > i) {
			// 剪枝,只要最后一个的值与结点的val对不上,那么说明中间少结点了,避免后面的循环
			if (nodes[nodes.size() - 1]->val != nodes.size())
				break;
			if (nodes[i]->left) {
				nodes[i]->left->val = nodes[i]->val * 2;
				nodes.push_back(nodes[i]->left);
			}
			if (nodes[i]->right) {
				nodes[i]->right->val = nodes[i]->val * 2 + 1;
				nodes.push_back(nodes[i]->right);
			}
			i++;

		}
		return nodes[nodes.size() - 1]->val == nodes.size();
	}
	void print(vector< TreeNode *> nodes) {
		for (int i = 0; i < nodes.size(); i++)
		{
			cout << nodes[i]->val << "  ";
		}
		cout << endl;
	}
};

int main()
{
	TreeNode *root8 = new TreeNode;
	TreeNode *root7 = new TreeNode;
	TreeNode *root6 = new TreeNode;
	TreeNode *root5 = new TreeNode;
	TreeNode *root4 = new TreeNode;
	TreeNode *root3 = new TreeNode(0, NULL, root7);
	TreeNode *root2 = new TreeNode(0,root4,root5);
	TreeNode *root1 = new TreeNode(0, root2, root3);;

	Solution sln;
	int flag = sln.isCompleteTree(root1);

	cout << flag << endl;
	return 0;
}