[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二
Given the root
of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]
. -1000 <= Node.val <= 1000
从底部层序遍历其实还是从顶部开始遍历,只不过最后存储的方式有所改变,可以参见博主之前的博文 Binary Tree Level Order Traversal, 参见代码如下:
解法一:
class Solution { public: vector<vector<int> > levelOrderBottom(TreeNode* root) { if (!root) return {}; vector<vector<int>> res; queue<TreeNode*> q{{root}}; while (!q.empty()) { vector<int> oneLevel; for (int i = q.size(); i > 0; --i) { TreeNode *t = q.front(); q.pop(); oneLevel.push_back(t->val); if (t->left) q.push(t->left); if (t->right) q.push(t->right); } res.insert(res.begin(), oneLevel); } return res; } };
下面来看递归的解法,由于递归的特性,我们会一直深度优先去处理左子结点,那么势必会穿越不同的层,所以当要加入某个结点的时候,必须要知道当前的深度,所以使用一个变量 level 来标记当前的深度,初始化带入0,表示根结点所在的深度。由于需要返回的是一个二维数组 res,开始时由于不知道二叉树的深度,不知道有多少层,所以无法实现申请好二维数组的大小,只有在遍历的过程中不断的增加。那么什么时候该申请新的一层了呢,当 level 等于二维数组的大小的时候,为啥是等于呢,不是说要超过当前的深度么,这是因为 level 是从0开始的,就好比一个长度为n的数组A,你访问 A[n] 是会出错的,当 level 等于数组的长度时,就已经需要新申请一层了,新建一个空层,继续往里面加数字,参见代码如下:
解法二:
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> res; levelorder(root, 0, res); return vector<vector<int>> (res.rbegin(), res.rend()); } void levelorder(TreeNode* node, int level, vector<vector<int>>& res) { if (!node) return; if (res.size() == level) res.push_back({}); res[level].push_back(node->val); if (node->left) levelorder(node->left, level + 1, res); if (node->right) levelorder(node->right, level + 1, res); } };
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/
相关文章
- [LeetCode] Binary Tree Level Order Traversal 二叉树层次遍历(DFS | BFS)
- Java实现 LeetCode 732 我的日程安排表 III(暴力 || 二叉树)
- Java实现 LeetCode 729 我的日程安排表 I(二叉树)
- Java实现 LeetCode 729 我的日程安排表 I(二叉树)
- Java实现 LeetCode 680 验证回文字符串 Ⅱ(暴力)
- Java实现 LeetCode 655 输出二叉树(DFS+二分)
- Java实现 LeetCode 606 根据二叉树创建字符串(遍历树)
- Java实现 LeetCode 145 二叉树的后序遍历
- Java实现 LeetCode 144 二叉树的前序遍历
- Java实现 LeetCode 103 二叉树的锯齿形层次遍历
- Java实现 LeetCode 103 二叉树的锯齿形层次遍历
- Java实现 LeetCode 102 二叉树的层次遍历
- Java实现 LeetCode 101 对称二叉树
- Java实现 LeetCode 106 从中序与后序遍历序列构造二叉树
- 【二叉树】LeetCode 102. 二叉树的层序遍历【中等】
- LeetCode(103): 二叉树的锯齿形层次遍历
- leetcode 101. 对称二叉树 js实现
- 【Leetcode刷题Python】94. 二叉树的中序遍历
- 【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- LeetCode 94. 二叉树的中序遍历
- 【LeetCode】226. 翻转二叉树
- 【LeetCode】543. 二叉树的直径
- 【LeetCode】236. 二叉树的最近公共祖先