LeetCode(107): 二叉树的层次遍历 II
2023-09-14 08:59:35 时间
Easy!
题目描述:
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回其自底向上的层次遍历为:
[ [15,7], [9,20], [3] ]
解题思路:
从底部层序遍历其实还是从顶部开始遍历,只不过最后存储的方式有所改变,参见http://www.cnblogs.com/grandyang/p/4051321.html,代码如下:
C++解法一:
1 // Iterative 2 class Solution { 3 public: 4 vector<vector<int> > levelOrderBottom(TreeNode *root) { 5 vector<vector<int> > res; 6 if (root == NULL) return res; 7 8 queue<TreeNode*> q; 9 q.push(root); 10 while (!q.empty()) { 11 vector<int> oneLevel; 12 int size = q.size(); 13 for (int i = 0; i < size; ++i) { 14 TreeNode *node = q.front(); 15 q.pop(); 16 oneLevel.push_back(node->val); 17 if (node->left) q.push(node->left); 18 if (node->right) q.push(node->right); 19 } 20 res.insert(res.begin(), oneLevel); 21 } 22 return res; 23 } 24 };
下面我们来看递归的解法,核心就在于我们需要一个二维数组,和一个变量level,当level递归到上一层的个数,我们新建一个空层,继续往里面加数字。
C++解法二:
1 // Recurive 2 class Solution { 3 public: 4 vector<vector<int>> levelOrderBottom(TreeNode* root) { 5 vector<vector<int> > res; 6 levelorder(root, 0, res); 7 return vector<vector<int> > (res.rbegin(), res.rend()); 8 } 9 void levelorder(TreeNode *root, int level, vector<vector<int> > &res) { 10 if (!root) return; 11 if (res.size() == level) res.push_back({}); 12 res[level].push_back(root->val); 13 if (root->left) levelorder(root->left, level + 1, res); 14 if (root->right) levelorder(root->right, level + 1, res); 15 } 16 };
相关文章
- ☆打卡算法☆LeetCode 222. 完全二叉树的节点个数 算法解析
- LeetCode笔记:Weekly Contest 309
- LeetCode第三题,五个版本迭代优化带你吃透two pointers算法
- LeetCode刷题系列(3)
- leetcode-103二叉树的锯齿形层序遍历「建议收藏」
- leetcode二叉树的层次遍历_完全二叉树的中序序列
- LeetCode笔记:Weekly Contest 314
- leetcode 206. 反转链表 js实现
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇
- LeetCode笔记:Weekly Contest 317
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇_2023-02-28
- js分类刷leetcode动态规划
- LeetCode - #74 搜索二维矩阵
- 前端工程师leetcode算法之二叉树的构造和遍历
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇5
- LeetCode——二叉树的非递归遍历