LeetCode: Binary Tree Inorder Traversal

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

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

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

---

There is a method called Morris traversal that can traverse the binary tree iteratively. It each time make a node's left child's right most pointer point to it self. More explanations please read the reference.

C++ Code:

/*
 * func: inorder_traversal
 * goal: traverse the tree in inorder
 * @param root: root node of the tree
 * return: inorder traversal of the tree
 */
/*
 * Morris Traversal
 * complexity: time O(n), space O(1)
 */
vector<int> inorder_traversal(TreeNode *root){
    vector<int> result;
    if(root == nullptr){
        return result;
    }
    
    TreeNode *curr = root;
    while(curr != nullptr){
        if(curr->left == nullptr){
            result.emplace_back(curr->val);
            curr = curr->right;
        }else{
            TreeNode *pre = curr->left;
            while(pre->right != nullptr && pre->right != curr){
                pre = pre->right;
            }
            
            if(pre->right == nullptr){
                pre->right = curr;
                curr = curr->left;
            }else{
                pre->right = nullptr;
                result.emplace_back(curr->val);
                curr = curr->right;
            }
        }
    }
    
    return result;
}

Python Code:

# func: inorder traversal of binary tree
# @param root: root node of the binary tree
# @result: a list of the val in inorder
def inorder_traversal(root):
    result = []
    if not root:
        return result

    curr = root
    while curr:
        if not curr.left:
            result.append(curr.val)
            curr = curr.right
        else:
            pre = curr.left
            while pre.right and pre.right != curr:
                pre = pre.right

            if not pre.right:
                pre.right = curr
                curr = curr.left
            else:
                pre.right = None
                result.append(curr.val)
                curr = curr.right
    return result

Reference Link:

1. Inorder Tree Traversal without recursion and without stack! | GeeksforGeeks: http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

2. Tree traversal - Wikipedia, the free encyclopedia: http://en.wikipedia.org/wiki/Tree_traversal#Morris_in-order_traversal_using_threading

3. 精妙的Morris二叉树遍历算法: http://daiziguizhong.qiniudn.com/article22.html