94. Binary Tree Inorder Traversal

Given a binary tree, return theinordertraversal of its nodes' values.

For example: Given binary tree[1,null,2,3],

   1
    \
     2
    /
   3

return[1,3,2].

Note:Recursive solution is trivial, could you do it iteratively?

Trivial Solution: According to the definition of Inorder (O(n) time and O(n) space, for the function call stack)

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

        inorderTraversalHelper(root);
        return answer;        
    }

    void inorderTraversalHelper(TreeNode * root){
        if(!root) return;
        inorderTraversalHelper(root->left);
        answer.push_back(root->val);
        inorderTraversalHelper(root->right);
    }
};

Thoughts

1. Using Stack to keep track path

2. *Morris traversal

Code Using Stack: (O(n) time and O(n) space)

/**
 * 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 {
    stack<TreeNode *> path;
    vector<int> answer;
public:
    vector<int> inorderTraversal(TreeNode* root) {

        traverse(root);
        return answer;
    }

    void traverse(TreeNode* cur){
        while(cur || !path.empty()){
            // first to the left
            while(cur){
                path.push(cur);
                cur = cur -> left;
            }
            // left done , do cur
            cur = path.top(); path.pop();
            answer.push_back(cur->val);
            // exploring right
            cur = cur->right;
        }
    }
};

Code with Morris Traversal: O(n) time and O(1) space (two assisting pointers)!

psudo-code (Thanks monkeykingyan's solution)

Step1. Initialize current as root
Step2. While current is not NULL
  If current does not have left child
  a. Add current’s value
  b. Go to the right, i.e., current = current.right
 Else
  a. In current's left subtree, make current the right child of the rightmost node
  b. Go to this left child, i.e., current = current.left

Code

/**
 * 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> answer;
        TreeNode *cur = root; 
        while(cur){

            if(cur->left){
                TreeNode* pre = cur -> left;
                while(pre -> right) pre = pre -> right;
                pre->right = cur;
                TreeNode * temp = cur;
                cur = cur -> left;
                temp -> left = NULL;
            }
            else{
                answer.push_back(cur->val);
                cur = cur -> right;
            }
        }
         return answer;
    }
};

Talonj @ Stackoverflow explaination:

Special Thanks jianchaolifighter for the reference