题目描述
题目链接:107. Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
例子
Input: [3,9,20,null,null,15,7]
Output:
1 2 3 4 5
| [ [15,7], [9,20], [3] ]
|
解题思路
通过 BFS 按层输出节点,最后逆转得到的向量即可,代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
#include <algorithm> #include <queue> #include <vector>
class Solution { public: std::vector<std::vector<int>> levelOrderBottom(TreeNode *root) { std::vector<std::vector<int>> result; if (root == nullptr) return result;
std::queue<TreeNode *> q; q.psuh(root); while (!q.empty()) { std::queue<TreeNode *> next_q; std::vector<int> level; while (!q.empty()) { TreeNode *node = q.front(); q.pop();
level.push_back(node->val); if (node->left) next_q.push(node->left); if (node->right) next_q.push(node->right); } result.push_back(level); level.clear(); std::swap(q, next_q); }
std::reverse(result.begin(), result.end());
return result; } };
|
- 时间复杂度: O(n)
- 空间复杂度: O(w) — 每层最大宽度
GitHub 代码同步地址: 107.BinaryTreeLevelOrderTraversalIi.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions