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

For example:

Given binary tree {1,#,2,3},

非递归版本：

用一个栈来模拟递归的情况，

首先思考inorder traverse的递归函数

traverse(left tree);

visit current node

traverse(right tree);

也就是说我们把一个节点压入栈中，首先它会先递归访问左子树（左节点入栈），再访问本身（这个时候这个节点就可以出栈了）,在访问右子树（右节点入栈）。

最后我们定义一个数据结构

1 struct Node2 {3     TreeNode *tNode;4     bool findLeft;5     Node(){}6     Node(TreeNode *n):tNode(n), findLeft(false){}7 };

其中findLeft是判断是否已将左节点入栈了

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 struct Node11 {12     TreeNode *tNode;13     bool findLeft;14     Node(){}15     Node(TreeNode *n):tNode(n), findLeft(false){}16 };17 18 class Solution {19 private:20     vector
     
       ret;21 public:22     vector
      
        inorderTraversal(TreeNode *root) {23         // Start typing your C/C++ solution below24         // DO NOT write int main() function25         stack
       
         s;26         s.push(Node(root, false));27         ret.clear();28         29         while(!s.empty())30         {31             Node node = s.top();32             if (node.tNode == NULL)33                 s.pop();34             else35             {36                 if (!node.findLeft)37                 {38                     s.pop();39                     s.push(Node(node.tNode, true));40                     s.push(Node(node.tNode->left, false));41                 }42                 else43                 {44                     s.pop();45                     ret.push_back(node.tNode->val);46                     s.push(Node(node.tNode->right, false));47                 }48             }49         }50         51         return ret;52     }53 };
       
      
     

 

递归版本：

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 private:12     stack
     
       s;13     vector
      
        ret;14 public:15     vector
       
         inorderTraversal(TreeNode *root) {16         // Start typing your C/C++ solution below17         // DO NOT write int main() function18         ret.clear();19         if (root == NULL)20             return ret;21             22         s.push(root);23         TreeNode *node = root;24         while(!s.empty())25         {26             node = node->left;27             s.push(node);28         }29     }30 };