前言
明白完全二叉树的定义之后,根据特性来进行遍历即可。
难的地方在于DFS和BFS吧
题目
给定一个二叉树,确定他是否是一个完全二叉树。
完全二叉树的定义:若二叉树的深度为 h,除第 h 层外,其它各层的结点数都达到最大个数,第 h 层所有的叶子结点都连续集中在最左边,这就是完全二叉树。(第 h 层可能包含 [1~2h] 个节点)
数据范围:节点数满足 1 ≤ n ≤ 100 1≤n≤100 1≤n≤100
示例1
输入:
{ 1 , 2 , 3 , 4 , 5 , 6 } \{1,2,3,4,5,6\} {1,2,3,4,5,6}
返回值:
t r u e true true
示例2
输入:
{ 1 , 2 , 3 , 4 , 5 , # , 6 } \{1,2,3,4,5,\#,6\} {1,2,3,4,5,#,6}
返回值:
f a l s e false false
解决方案一
1.1 思路阐述
对于一棵树,如果只有一个节点,那么他就是完全二叉树。
在同等高度下,叶子结点一定是从左往右排,如果出现左边为空,右边有叶子结点的情况,即为非叶子结点。
我们首先用层次遍历的方式来做,这个层次遍历其实和我们上面给的样例中的输入一样。先插入根节点,接着是它对应的子节点,先左再右。
我们按序遍历,只要找到第一个为空的节点,那么就找到了临界点。比如上面例二中,3的左孩子为空,有孩子为6.其实我们找到了3的左孩子为空的情况,那么只要这个节点右边出现节点,无论是同级还是下一级,都不满足完全二叉树。
举个例子,3的左节点为7,如果7为空,那么层次遍历的时候,在队列中如果7后面还有节点,那么一定不满足完全二叉树。后面有节点的情况可以分为同级的6以及下一层级的8。
1.2 源码
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
//空树一定是完全二叉树
if(root == NULL)
return true;
queue<TreeNode*> q;
//根节点先访问
q.push(root);
//定义一个首次出现的标记位
bool flag = false;
//层次遍历
while(!q.empty()){
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* cur = q.front();
q.pop();
//标记第一次遇到空节点
if (cur == NULL)
flag = true;
else{
//后续访问已经遇到空节点了,说明经过了叶子
if (flag) return false;
q.push(cur->left);
q.push(cur->right);
}
}
}
return true;
}
};
总结
二叉树的常规解法是递归,但这里递归我一开始也尝试过,只能处理同一条分支的情况,无法比较左右两侧。
二叉树的遍历通常使用层次遍历或者深搜遍历。