用C++实现二叉树层序遍历
导读:本文共1527字符,通常情况下阅读需要5分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 二叉树层序遍历从底部层序遍历其实还是从顶部开始遍历,只不过最后存储的方式有所改变,可以参见博主之前的博文 Binary Tree Level Order Traversal, 参见代码如下:解法一:classSolution{public:vector<vector<int>>levelOrderBottom(TreeNode*roo... ...
目录
(为您整理了一些要点),点击可以直达。从底部层序遍历其实还是从顶部开始遍历,只不过最后存储的方式有所改变,可以参见博主之前的博文 Binary Tree Level Order Traversal, 参见代码如下:
解法一:
下面来看递归的解法,由于递归的特性,我们会一直深度优先去处理左子结点,那么势必会穿越不同的层,所以当要加入某个结点的时候,必须要知道当前的深度,所以使用一个变量 level 来标记当前的深度,初始化带入0,表示根结点所在的深度。由于需要返回的是一个二维数组 res,开始时由于不知道二叉树的深度,不知道有多少层,所以无法实现申请好二维数组的大小,只有在遍历的过程中不断的增加。那么什么时候该申请新的一层了呢,当 level 等于二维数组的大小的时候,为啥是等于呢,不是说要超过当前的深度么,这是因为 level 是从0开始的,就好比一个长度为n的数组A,你访问 A[n] 是会出错的,当 level 等于数组的长度时,就已经需要新申请一层了,新建一个空层,继续往里面加数字,参见代码如下:
解法二:
Github 同步地址:
https://github.com/grandyang/leetcode/issues/107
类似题目:
Average of Levels in Binary Tree
Binary Tree Zigzag Level Order Traversal
Binary Tree Level Order Traversal
类似题目:
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/discuss/35089/Java-Solution.-Using-Queue
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/discuss/34981/My-DFS-and-BFS-java-solution
用C++实现二叉树层序遍历的详细内容,希望对您有所帮助,信息来源于网络。