前言-新方法尝试
以前学完知识或写完算法题后,直接就写博客记录下来。
然而因为记录完博客后,以为知识都记住了,就没有再管。
但过了不久,知识和算法就只记得五成了,典型的掌握不牢固。
所以今天试一试新的方法,在学完知识或做完题后,不要急着记下来,而是每天晚上抽一段时间,重新做一遍题,想一遍知识,再将今天学到的知识或解题思路总结成博客。
每过三五天,再回头看一遍博客来加深印象,慢慢吃透。
过一段时间和大家反馈效果。
今天分享一个经典算法:二叉树的广度优先搜索:层序遍历。
【这道题同时也是牛客网的NC15,有兴趣的朋友可以搜题号】
一、层序遍历
设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,
首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,
以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
如下面这棵树:
其层序遍历的结果即为:3,9,20,15,7。
二、思路
对于二叉树的层序遍历,我们需要用到队列这个数据结构:
进行判空操作,如果根节点为NULL,则直接return。
创建一个vector容器,存放最终的结果。
再创建一个queue容器,用队列存储结点。
首先,根节点入队:
然后,进行一个大的while循环,循环条件是当前队列不为空。
建立一个临时vector<int>容器,存放当前层结点的值;
然后创建一个number,记录当前队列中的元素个数,也就是当前层的元素个数。
进行一个for循环,次数为当前层的元素个数。
每一次循环,都将该元素先用一个临时指针记录,出队;
然后再将利用临时指针,将该元素的值写进本层vector中。
再依次让其左右孩子入队。
这样for循环一轮后,本层的元素全部出队,并按顺序记录到了最终的结果集中;
而下一层的元素全部入队。
直到总队列为空,代表所有元素已遍历完成。
最后用迭代器输出一下结果集容器即可。
三、代码
//层序遍历
void levelOrder(Tree t)
{
if (t == NULL)
{
return;
}
//向量容器,存放层序遍历结果
vector<int> result;
//用队列存储结点
queue<Node*> q;
//根节点入队
q.push(t);
//只要当前队列不为空
while (!q.empty())
{
//用于存储当前遍历这一层的结点
vector<int> temp;
//记录当前队列内的元素个数
int n = q.size();
//开始循环,依次将本层的元素出队,
//并且让本层元素的左右孩子入队。
for (int i = 0; i < n; i++)
{
//临时结点,用来存放本层的各元素
Node* cur = q.front();
//本层第i+1个元素出队
q.pop();
//本层第i+1个元素的值存进temp中
temp.push_back(cur->data);
//左右孩子入队
if (cur->left != NULL)
{
q.push(cur->left);
}
if (cur->right != NULL)
{
q.push(cur->right);
}
}
//将本层结果保存到结果向量容器中
for (vector<int>::iterator it = temp.begin(); it != temp.end(); it++)
{
result.push_back(*it);
}
}
for (vector<int>::iterator it = result.begin(); it != result.end(); it++)
{
cout << *it << " ";
}
}
四、测试
测试代码:
int main()
{
Tree t = NULL;
Tree* tt = &t;
insert(tt, 5);
insert(tt, 3);
insert(tt, 4);
insert(tt, 8);
insert(tt, 9);
insert(tt, 1);
levelOrder(t);
releaseTree(t);
return 0;
}
运行截图: