算法Day12-层次遍历二叉树

2019-11-14 08:51:13

字体：大中小

来源：转载

供稿：网友

题目

给定一个二叉树，返回其节点值的层次遍历（即从左到右，一层一层遍历）例如：给定二叉树{3,9,20,#,#,15,7} 3 / / 9 20 / / 15 7 返回层次遍历如下： [ [3], [9,20] [15,7] ]

解析

通过广度优先遍历来实现层次遍历。创建一个Queue来缓存每一层的树节点，在遍历Queue的过程中，每取出一个元素，将该元素的左右子节点按顺序插入到Queue中。一直遍历下去，直到Queue为空。

代码

vector< vector<int> >levelOrder(TreeNode *root){ vector< vector<int> > result; if(root == NULL) return result; queue<TreeNode*> nodeQ; //先进先出(FIFO) 队列类型的nodeQ变量用来缓存每一层的数节点 nodeQ.push(root); //push int nextLevelCnt=0, currentLeveCnt=1; vector<int> layer; //layer存放的为某一层的节点数值，通过layer作为中间变量加入到result int visitedCnt=0; //访问过的节点数目 while(nodeQ.size() != 0) // 队列不为空时访问，否则返回结果 { TreeNode* node = nodeQ.front(); nodeQ.pop(); visitedCnt++; layer.push_back(node->val); if(node->left != NULL) //为空时不做处理 { //不为空则进队列 nodeQ.push(node->left); nextLevelCnt++; } if(node->right != NULL) { nodeQ.push(node->right); nextLevelCnt++; } if(visitedCnt == currentLeveCnt) //访问过的节点等于该层节点数时，开始下一层的访问。 { //下一层访问开始，visitedCnt置0，当前层数节点数为上层的nextLevelCnt数，nextLevelCnt置0 visitedCnt = 0; currentLeveCnt = nextLevelCnt; nextLevelCnt = 0; result.push_back(layer); //将上层的节点加入结果 layer.clear(); } } return result;}

上一篇：Servlet学习 ——Web部分第十天

下一篇：588A. Duff and Meat

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注