0094 Binary Tree Inorder Traversal

Problem Description

Given a binary tree, return the inorder traversal of its nodes' values.
Example

Input: [1,null,2,3]
1
\
 2
/
3
Output: [1,3,2]

Solution

Please refer this post for more details on the BST and traversal methods. Below will give three common methods to do the traversal.

Recursive Method

Simply follow the traversal order and call the function recursively:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        static vector<int> rlt;
        if(root == nullptr) return rlt;
        inorderTraversal(root->left);
        rlt.push_back(root->val);
        inorderTraversal(root->right);
        return rlt;
    }
};

iterative Method with stack

We collect nodes into the stack when we go top-down on the left sub-tree, whenever meet a null, we pop the top node from the stack, visit it and try the right sub-tree.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> rlt={};
        stack<TreeNode*> stk;
        while(!stk.empty() || root){
            while(root){
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            rlt.push_back(root->val);
            root = root->right;
        }
        return rlt;
    }
};

Morris Method

Morris method basically add a few links to help us easily go from leaves to its grand-parent node: for each node N, link the inorder predecessor P of N to the current node N: p->right = N if N has a left sub-tree, such that we could always follow the right child to get the next order node. Note in this method, we use left link to reach the smaller value, and use right link to reach larger value. An example code is the following:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> nodes;
        while (root) {
            if (root -> left) { // if the node has left node, we will do `p->right = N`
                TreeNode* pre = root -> left;
                while (pre -> right && pre -> right != root) { // pre is the inorder predecessor of root.
                    pre = pre -> right;
                }
                if (!pre -> right) { // link it
                    pre -> right = root;
                    root = root -> left;
                } else { // this is to check the right link is the one we added before
                    pre -> right = NULL; // so delete this link to keep the structure the same as before
                    nodes.push_back(root -> val);
                    root = root -> right; // always go right whenever we print a node
                }
            } else { // the node does not have left, meaning the current node is the smallest value, print it
                nodes.push_back(root -> val);
                root = root -> right; // go right always after printing a node
            }
        }
        return nodes;
    }
};