LeedCode OJ --- Binary Tree Inorder Traversal
5444 ワード
クリックしてタイトルリンクを開く
今日は再帰的なバージョンを書いただけで、まだ反復で実現する方法を考えていないので、書くことができる過程で、私のコードはACができますが、少し疑問があります.
問題は、プライマリコール関数は、サブ関数で返すサブ関数で定義できるvectorである.被変調関数の実行が終了すると、その割り当てられた空間は解放されるべきだと思いますので、被変調関数で定義された変数も主変調関数では使用できません...C++の基礎知識がまた忘れてしまったのかもしれませんが、暇があれば拾います.
コード(再帰版):
今日は反復法を用いて二叉木の中順遍歴を実現し,まず左サブツリーの最下層のノード(二叉木の最左側のノード)に反復し,経路上のノードをスタックに押し込み,次にスタックから要素をポップアップして結果(ans)に加え,右サブツリーを遍歴することを構想した.
コード(再帰版以外):
今日は再帰的なバージョンを書いただけで、まだ反復で実現する方法を考えていないので、書くことができる過程で、私のコードはACができますが、少し疑問があります.
問題は、プライマリコール関数は、サブ関数で返すサブ関数で定義できるvectorである.被変調関数の実行が終了すると、その割り当てられた空間は解放されるべきだと思いますので、被変調関数で定義された変数も主変調関数では使用できません...C++の基礎知識がまた忘れてしまったのかもしれませんが、暇があれば拾います.
コード(再帰版):
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> ans;
if (root == NULL) return ans;
if (root->left == NULL && root->right == NULL) {
ans.push_back(root->val);
return ans;
}
if (root->left != NULL) {
ans = inorderTraversal(root->left);
}
ans.push_back(root->val);
if (root->right != NULL) {
vector<int> tmp = inorderTraversal(root->right);
for (unsigned int i = 0; i < tmp.size(); i++)
ans.push_back(tmp[i]);
}
return ans;
}
};
今日は反復法を用いて二叉木の中順遍歴を実現し,まず左サブツリーの最下層のノード(二叉木の最左側のノード)に反復し,経路上のノードをスタックに押し込み,次にスタックから要素をポップアップして結果(ans)に加え,右サブツリーを遍歴することを構想した.
コード(再帰版以外):
1 class Solution {
2 public:
3 vector<int> inorderTraversal(TreeNode *root) {
4 int tail = 0;
5 vector<TreeNode*> Stack;
6 vector<int> ans;
7 TreeNode *T = root;
8 while (T != NULL || tail) {
9 while (T != NULL) {
10 tail++;
11 Stack.push_back(T);
12 T = T->left;
13 }
14 T = Stack[--tail];
15 Stack.pop_back();
16 ans.push_back(T->val);
17 T = T->right;
18 }
19
20 return ans;
21 }
22 };