版權聲明:轉載請聯系本人,感謝配合!本站位址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50560004
翻譯
給定一個二叉樹,傳回從下往上周遊經過的每個節點的值。
從左往右,從葉子到節點。
例如:
給定的二叉樹是 {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
傳回它從下往上的周遊結果:
[
[15,7],
[9,20],
[3]
]
原文
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).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
分析
其實吧,不管是從上到下還是從下到上都無所謂啦,最後反轉一下就好了,關鍵還是在于如何去周遊。
我一開始沒了解好題意,結果是按節點下面的兩個葉子來添加到vector的,後來發現原來是應該按層級。
是以采用了先進先出的隊列,隊列裡要包含二叉樹的層級資訊,是以構造一個pair。
vector<vector<int>> vecAns;
if (!root) return vecAns;
queue<pair<int, TreeNode*>> queueTree;
首先定義了用于最後傳回的vecAns,而後判斷root是否為空,是的話直接傳回不做添加操作。構造的queue中int用于存放層級資訊,TreeNode*用于存放節點。
接下來定義了map,它的優勢在于可以随時指定鍵來添加值,這裡就是指定層級來添加資訊,後面的是vector就是用于存放樹節點的。root的層級設定為0,後面用make_pair來構造pair對,最後添加到queue中。
map<int, vector<int>> mapAns;
int rootLevel = 0;
queueTree.push(make_pair(rootLevel, root));
隻要queue不為空就一直循環。每次一開始就解析出目前隊列頂部的層級資訊以及目前節點,将它添加到map中。添加完之後就可以彈出了。繼續判斷左右子樹,如果為空就先添加到queue中等待下一部操作。待到下一次循環時,就是将它們添加到map中了。
while (!queueTree.empty()) {
int currentLevel = (queueTree.front().first);
TreeNode *currentNode = (queueTree.front().second);
mapAns[currentLevel].push_back(currentNode->val);
queueTree.pop();
if (currentNode->left != NULL)
queueTree.push(make_pair(currentLevel + 1, currentNode->left));
if (currentNode->right != NULL)
queueTree.push(make_pair(currentLevel + 1, currentNode->right));
}
将map中的資訊逐個push到vector裡,最後就直接return了。
for (auto iter = mapAns.rbegin(); iter != mapAns.rend(); ++iter) {
vecAns.push_back(iter->second);
}
return vecAns;
Ok,大家可以去看看上一題:
LeetCode 102 Binary Tree Level Order Traversal(二叉樹的層級順序周遊)(*)代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode *root) {
vector<vector<int>> vecAns;
if (!root) return vecAns;
queue<pair<int, TreeNode*>> queueTree;
map<int, vector<int>> mapAns;
int rootLevel = 0;
queueTree.push(make_pair(rootLevel, root));
while (!queueTree.empty()) {
int currentLevel = (queueTree.front().first);
TreeNode *currentNode = (queueTree.front().second);
mapAns[currentLevel].push_back(currentNode->val);
queueTree.pop();
if (currentNode->left != NULL)
queueTree.push(make_pair(currentLevel + 1, currentNode->left));
if (currentNode->right != NULL)
queueTree.push(make_pair(currentLevel + 1, currentNode->right));
}
for (auto iter = mapAns.rbegin(); iter != mapAns.rend(); ++iter) {
vecAns.push_back(iter->second);
}
return vecAns;
}
};