LeedCode OJ --- Binary Tree Inorder Traversal

今天只是写了递归的版本，因为还没想好怎么用迭代来实现，可以写的过程中，有一点是有疑问的，虽然我的代码可以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 };