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?

分析：迭代版inorder traversal。对于任何一棵树，其最先被访问的是路径是最左侧的路径，在该最左侧路径上访问顺序呢是从叶子结点到根节点，很自然我们可以用一个stack保存这个路径。同时如果当前访问结点有右孩子，我们需把以右孩子为根的子树最左路径压入栈中。时间复杂度为O(n)，空间复杂度为O(h)。代码如下：

1 class Solution { 2 public: 3     vector
     
       inorderTraversal(TreeNode *root) { 4         vector
      
        result; 5         if(!root) return result; 6          7         stack
       
         S; 8         for(TreeNode *p = root; p; p = p->left) 9             S.push(p);10         11         while(!S.empty()){12             TreeNode *tmp = S.top();13             S.pop();14             result.push_back(tmp->val);15             for(TreeNode *p = tmp->right; p ; p = p->left)16                 S.push(p);17         }18         19         return result;20     }21 };
       
      
     

 Morris中序遍历：

class Solution {public:    vector
     
       inorderTraversal(TreeNode *root) {        vector
      
        result;        TreeNode * prev = NULL, *cur = root;                while(cur != NULL){            if(cur->left == NULL){                result.push_back(cur->val);                cur = cur->right;            }else{                for(prev = cur->left; prev->right != NULL && prev->right != cur; prev = prev->right);                if(prev->right == NULL){                    prev->right = cur;                    cur = cur->left;                }else{                    prev->right = NULL;                    result.push_back(cur->val);                    cur = cur->right;                }            }        }                return result;    }};