LeetCode 94. Binary Tree Inorder Traversal [Medium] [C++] 解題筆記

這題要我們找一個 Tree 的中序排序。

EX:

        Input: [1,null,2,3]

       1
        \
         2
        /
       3

       Output: [1,3,2]

想法:

    Tree 的 inorder traverse (中序遍歷)用 recursive 的方式非常直覺簡單，因此這題主要想考查的應該是

用 iterative 的方式來實作，基本上 recursive 與 iterative 的方法之間都可以互相轉換只是直覺與否而已。

另外上述的實作方法都需要使用到額外的空間(stack) 來儲存尚未走訪的 node，如果使用Morris Traversal

就可以在 O(1) space 限制下完成 inorder traversal。

Complexity: O(n) time, O(n)/O(1) space.

完整程式碼:

解法一(recursive):

class Solution {
public:
    void dfs(vector<int>& inorder, TreeNode* root) {
        if (root == NULL) { return; }
        dfs(inorder, root->left);
        inorder.emplace_back(root->val);
        dfs(inorder, root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> inorder;
        dfs(inorder, root);
        return inorder;
    }
};

解法二(iterative + stack):

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> inorder;
        if (root == NULL) { return inorder; }
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()) {
            auto cur = s.top();
            if (cur->left == NULL) {
                inorder.emplace_back(cur->val);
                s.pop();
                if (cur->right != NULL) {
                    s.push(cur->right);
                }       
            }
            else {
                s.push(cur->left);
                cur->left = NULL;
            }
        }
        return inorder;
    }
};

解法三(Morris Traversal):

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode* cur = root;
        
        while (cur != nullptr) {
            if (cur->left == nullptr) {
                res.emplace_back(cur->val);
                cur = cur->right;
            }
            else {
                // find predecessor
                TreeNode* pre = cur->left;
                while (pre->right != nullptr && pre->right != cur) {
                    pre = pre->right;
                }
                // record predecessor 
                if (pre->right == nullptr) {
                    pre->right = cur;
                    cur = cur->left;
                }
                // whole left subtree of cur has been visited
                else {
                    pre->right = nullptr;
                    res.emplace_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};