本文主要是介绍[Tree Breadth First Search] 二叉树的层序遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
leetcode 102,Binary Tree Level Order Traversal,难度 medium
树上的BFS,Tree Breadth First Search这个标题更新,二叉树广度优先搜素算法处理的相关题目。
DFS(Deep First Search)深度优先搜索,BFS(Breath First Search)广度优先搜索的区别如下图。
0. 题干
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
1. 代码
/*** 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:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que; //构造队列que,里面的元素都是TreeNode*类型的指针que.push(root);vector<vector<int>> res; //二维数组while (que.size() != 0) {int size = que.size();vector<int> level;while (size --) {TreeNode* cur = que.front();que.pop();if (!cur) {continue;}level.push_back(cur->val);que.push(cur->left);que.push(cur->right);}if (level.size() != 0) {res.push_back(level);}}return res;}
};
2. 代码流程详叙
2.1 第一层
oot为结点1的地址(他里面的val值是3),
构造队列que,里面的元素都是TreeNode*类型的指针,
把root指针存到队列里面,
构造二维数组res,里面存储的元素int型,
此时que.size=1,进入最外面的while循环,
此时size=1;
定义一维数组level,
进入while(size --)循环,size–为0
cur存储结点1地址,
que.pop(),把刚才存到que里面的指针元素(结点1)地址清除,
cur地址存在,不为NULL,所以不管continue语句,
把结点1的val值存到level数组里面,再依次把结点1的左右结点的地址存到队列que里面去;
size为0,所以内while循环不继续,进入下面的if 语句,
此时level.size()为1,把level的地址存到res里面,即第一层二叉树的元素被存到res了。
2.2 第二层
que.size() 为2,进入最外面while循环,
size值为2,再定义一个数组level,注意这个level和之前的不一样,地址不同,
size为2,进入内while循环,size–为1,
cur指向结点1的左结点,即存储元素9的地址,
que队列清除元素9的地址,
cur不为NULL,所以还是别管continue;
把元素9存到level数组里面,
元素9对应结点的左右结点都没有,所以存了两个NULL进入队列;
再次内while循环,size–为0,
cur指向元素20对应的地址,
que队列清除元素20的地址,cur不为NULL,调过continue,
然后把元素20存到level数组里面,再把元素15、元素7对应的地址存到队列里面,
size为0,结束内while循环,
level.size()值为2,把存储了元素9、元素20的一维数组的地址,存到二维数组res里面,即第二层二叉树的元素被存好了。
2.3 第三层
que.size()为4,不为0,进入外面的while大循环,
size=4,
再次定义新的一维数组level,
size为4,进入内while循环,size–,为3.
cur指向NULL;
que队列清除一个NULL,
进入continue语句,跳过剩下的代码,继续下一个while循环,size–为2
cur指向下一个NULL,
还是走continue,调过剩下的代码,继续下一个while循环,size–为1
cur存储元素15对应的地址,
que队列清除元素15对应的地址,
把元素15存到新的一维数组level里面,把元素15对应结点的左右结点存到队列里面,就是存了两个NULL,
进入内while循环,size–为0,
cur存储元素7对应的地址,
que队列清除元素7对应的地址,跳过continue语句,
把元素7存到一维数组level里面,再把元素7的左右结点存到队列里面,就是再存了两个NULL,
level.size()为2,把依次存储了元素15、元素7的一维数组level,的地址存到二维数组res里面,即第三层二叉树的元素被存好了。
2.4 结束
还要再来一次判断:
que.size()为4,不为0,进入外面的while大循环,由于队列存了四个NULL,所以一直走四次continue语句,
level.size值为0,队列que一直pop,最终que.size()也为0,所有代码运行结束,
返回 res;
这篇关于[Tree Breadth First Search] 二叉树的层序遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!