LeetCode(107):二叉木の階層遍歴II
6102 ワード
Easy!
タイトルの説明:
ツリーを指定し、ノード値の下から上への階層遍歴を返します.(すなわち、リーフノードのある層からルートノードのある層まで、層ごとに左から右へ遍歴する)
たとえば、与えられたツリー
下から上への階層の遍歴を返します.
問題解決の考え方:
下のレイヤシーケンスからループするか、上のレイヤからループするかは、最後に格納する方法が変更されているだけです.http://www.cnblogs.com/grandyang/p/4051321.htmlコードは次のとおりです.
C++解法一:
次に、再帰的な解法を見てみましょう.核心は、2次元配列と変数levelが必要です.levelが前の層に再帰された個数になると、空の層を新規に作成し、数字を追加し続けます.
C++解法2:
転載先:https://www.cnblogs.com/ariel-dreamland/p/9162461.html
タイトルの説明:
ツリーを指定し、ノード値の下から上への階層遍歴を返します.(すなわち、リーフノードのある層からルートノードのある層まで、層ごとに左から右へ遍歴する)
たとえば、与えられたツリー
[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 vectorint> > levelOrderBottom(TreeNode *root) {
5 vectorint> > res;
6 if (root == NULL) return res;
7
8 queue 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 };
次に、再帰的な解法を見てみましょう.核心は、2次元配列と変数levelが必要です.levelが前の層に再帰された個数になると、空の層を新規に作成し、数字を追加し続けます.
C++解法2:
1 // Recurive
2 class Solution {
3 public:
4 vectorint>> levelOrderBottom(TreeNode* root) {
5 vectorint> > res;
6 levelorder(root, 0, res);
7 return vectorint> > (res.rbegin(), res.rend());
8 }
9 void levelorder(TreeNode *root, int level, vectorint> > &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 };
転載先:https://www.cnblogs.com/ariel-dreamland/p/9162461.html