# 94 - Binary Tree Inorder Traversal

解法一 - Recursive 解

用 recursive 解法的主要問題就是要 maintain 一個共同的 vector 來儲存結果，一種實作方法是在每一層都建立 vector，然後在上層合起來：

/**
 * 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<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;

        vector<int> l, r;
        l = inorderTraversal(root->left);
        r = inorderTraversal(root->right);
        res.insert(res.end(), l.begin(), l.end());
        res.push_back(root->val);
        res.insert(res.end(), r.begin(), r.end());

        return res;
    }
};

這種實作方法跑起來算快，不過記憶體就用比較多：

Runtime: 4 ms, faster than 90.43% of C++ online submissions for Binary Tree Inorder Traversal. Memory Usage: 11.1 MB, less than 5.01% of C++ online submissions for Binary Tree Inorder Traversal.

第二種做法是額外寫一個 helper function，然後把 vector reference 傳進去，程式寫起來會比較簡潔：

/**
 * 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<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        helper(root, res);

        return res;
    }

private:
    void helper(TreeNode* root, vector<int> &vec) {
        if(!root) return;

        helper(root->left, vec);
        vec.push_back(root->val);
        helper(root->right, vec);
    }
};

第二種做法的結果如下：

Runtime: 4 ms, faster than 90.43% of C++ online submissions for Binary Tree Inorder Traversal. Memory Usage: 9.6 MB, less than 11.65% of C++ online submissions for Binary Tree Inorder Traversal.

Recursive 解法的時間複雜度是：

i

解法二 - Iterative 解

另一種做法就是用 stack 來儲存 node，這樣就可以用 iterative 的方式來實作。用 stack 實作的思路可以用這樣來想：

1. 因為是 inorder，所以希望先把當前 node 的 left child node 塞到 stack 裡，然後繼續處理 left child node 是不是還有 left child，一路做到最左邊的 leaf node。

2. 如果要把某個 stack 裡的 node pop 掉，必須確定他的 left/right child 都已經被處理過了，因為第一步已經一路做到 left most leaf node，表示在 stack 中的 node 的 left child 都已經在 stack 中，所以 pop 出來之後要再把 pop 出來 node 的 right child 變成現在要處理的 node。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> vec;

        // Start traversing using stack
        TreeNode *cur = root;

        while(cur || !s.empty()) {
            while(cur) {
                s.push(cur);
                cur = cur->left;
            }

            cur = s.top();
            s.pop();
            vec.push_back(cur->val);
            cur = cur->right;
        }

        return vec;
    }
};

這種做法會拜訪每個 node 一次，而且 stack 也會都存到每個 node，所以時間和空間複雜度都是 O(n)。

跑起來的結果如下：

Runtime: 4 ms, faster than 90.43% of C++ online submissions for Binary Tree Inorder Traversal. Memory Usage: 9.2 MB, less than 57.23% of C++ online submissions for Binary Tree Inorder Traversal.

解法三 - Morris Traversal

這種解法太神奇了，留待之後有機會再看看ＸＤ

可以參考 Leetcode 的 solution。

i