94. Binary Tree Inorder Traversal

---

My Solution

Solution 1: DFS (recursion)

The Key Idea for Solving This Coding Question

C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        dfs(root);
        return inorder;
    }

private:
    vector<int> inorder;

    void dfs(TreeNode *root) {
        if (root == nullptr) {
            return;
        }

        dfs(root->left);
        inorder.push_back(root->val);
        dfs(root->right);
    }
};

Time Complexity

$O(n)$

$n$ is the number of nodes in the binary tree.

Space Complexity

$O(H)$

$H$ is the height of the binary tree.

Solution 2: DFS (iteration, stack)

The Key Idea for Solving This Coding Question

C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

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

        while (!st.empty() || root != nullptr) {
            if (root != nullptr) {
                st.push(root);
                root = root->left;
            } else {
                root = st.top();
                st.pop();

                inorder.push_back(root->val);
                root = root->right;
            }
        }

        return inorder;
    }
};

Time Complexity

$O(n)$

$n$ is the number of nodes in the binary tree.

Space Complexity

$O(H)$

$H$ is the height of the binary tree.

Solution 3: Morris Traversal

The Key Idea for Solving This Coding Question

1. 找到每個 non-leaf 之子樹樹根 (以 node 指標指向它) 的 predecessor (以 prev 指標指向它)。此時，這個 predecessor 必無右子樹 (或右節點)。將 predecessor 的 right 指標指向 node 。在我們走訪完左子樹中的所有節點後，可由此時 predecessor 的 right 指標回到目前 node 所指向的節點。所以這個演算法會走訪每個節點兩次。
2. 第 21 ~ 22 行是 node 所指向的節點沒有左子樹。此時，可以直接將節點的數值推入 inorder ，然後走向 node 所指向之節點的右子樹。
3. 第 25 ~ 27 行的 while 迴圈是在尋找 node 的 predecessor ，以 prev 指標指向它。
4. 第 25 ~ 27 行的 if-else 中，若 prev->right 為 nullptr ，表示 node 第一次走訪此節點。反之，表示 node 的左子樹已走訪完畢，可以把 node 所指向之節點的值推入 inorder ，往 node 所指向之節點的右子樹走。

C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
 *     TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> inorder;
        TreeNode *node = root;
        
        while (node) {
            if (!node->left) {
                inorder.push_back(node->val);
                node = node->right;
            } else {
                TreeNode *prev = node->left;
                while (prev->right != nullptr && prev->right != node) {
                    prev = prev->right;
                }
                
                if (prev->right == nullptr) {
                    prev->right = node;
                    node = node->left;
                } else {
                    inorder.push_back(node->val);
                    prev->right = nullptr;
                    node = node->right;
                }
            }
        }
        
        return inorder;
    }
};

Time Complexity

$O(n)$

$n$ is the number of nodes in the binary tree.

Space Complexity

$O(1)$

Miscellaneous

144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal

Test Case

[1,null,2,3]

[1,2,3,4,5,null,8,null,null,6,7,9]

[]

[1]

[4,2,7,1,3]

[18,2,22,null,null,null,63,null,84,null,null]

[18,6,22,5,7,11,63,1,2,9,8,10,24,12,84]

[2,3,null,1]

[1,2,3]

[4,2,1,3,7]

[18,2,22,63,84]

[18,6,5,1,2,7,9,8,22,11,10,24,63,12,84]

–>