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},

非递归版本：

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

首先思考inorder traverse的递归函数

traverse(left tree);

visit current node

traverse(right tree);

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

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

1 struct Node
2 {
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 Node
11 {
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<int> ret;
21 public:
22     vector<int> inorderTraversal(TreeNode *root) {
23         // Start typing your C/C++ solution below
24         // DO NOT write int main() function
25         stack<Node> 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             else
35             {
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                 else
43                 {
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<TreeNode* > s;
13     vector<int> ret;
14 public:
15     vector<int> inorderTraversal(TreeNode *root) {
16         // Start typing your C/C++ solution below
17         // DO NOT write int main() function
18         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 };