LeedCode OJ --- Binary Tree Inorder Traversal

5444 ワード

クリックしてタイトルリンクを開く
今日は再帰的なバージョンを書いただけで、まだ反復で実現する方法を考えていないので、書くことができる過程で、私のコードは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 };