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

Example:

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

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

 

Approach #1: recurisive.

/** * 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
     
       inorderTraversal(TreeNode* root) {        vector
      
        ans;        helper(root, ans);        return ans;    }    private:    void helper(TreeNode* root, vector
       
        & ans) {        if (root != NULL) {            if (root->left != NULL) {                helper(root->left, ans);            }            ans.push_back(root->val);            if (root->right != NULL) {                helper(root->right, ans);            }        }    }};
       
      
     

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Inorder Traversal.

 

Approach #2: Iteration with stack.[Java]

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List
     
       inorderTraversal(TreeNode root) {        List
      
        res =  new ArrayList< > ();        Stack
       
         stack = new Stack< > ();        TreeNode curr = root;        while (curr != null || !stack.isEmpty()) {            while (curr != null) {                stack.push(curr);                curr = curr.left;            }            curr = stack.pop();            res.add(curr.val);            curr = curr.right;        }        return res;    }}
       
      
     

Runtime: 

1 ms, faster than 60.30% of Java online submissions for Binary Tree Inorder Traversal.

 

Approach #3: Morris Traversal.[python] 

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def inorderTraversal(self, root):        """        :type root: TreeNode        :rtype: List[int]        """        res = []        curr = root        while curr:            if not curr.left:                res.append(curr.val)                curr = curr.right            else:                pre = curr.left                while pre.right:                    pre = pre.right                pre.right = curr                temp = curr                curr = curr.left                temp.left = None        return res

Runtime: 24 ms, faster than 40.09% of Python online submissions for Binary Tree Inorder Traversal.

 

 Analysis: [Morris Traversal]

In this method, we have to use a new data structure-Threaded Binary Tree, and the strategy is as follows:

Step 1: Initialize current as root

Step 2: 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

For example:

1        /   \       2     3      / \   /     4   5 6

First, 1 is the root, so initialize 1 as current, 1 has left child which is 2, the current's left subtree is

2        / \       4   5

So in this subtree, the rightmost node is 5, then make the current(1) as the right child of 5. Set current = cuurent.left (current = 2). The tree now looks like:

2        / \       4   5            \             1              \               3 / 6

For current 2, which has left child 4, we can continue with thesame process as we did above

4         \          2           \            5             \              1               \                3 / 6

then add 4 because it has no left child, then add 2, 5, 1, 3 one by one, for node 3 which has left child 6, do the same as above. Finally, the inorder taversal is [4,2,5,1,6,3].