# LeetCode题目：Binary Tree Inorder Traversal

By | 2012 年 9 月 14 日

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?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

代码

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
```
1. 递归解法
很简单，8ms过小集合，12ms过大集合

```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector result;
if (NULL == root)
return result;
vector leftResult = inorderTraversal(root->left);
vector rightResult = inorderTraversal(root->right);
for( int i = 0 ; i < leftResult.size(); ++i)
result.push_back(leftResult[i]);
result.push_back(root->val);
for( int i = 0 ; i < rightResult.size(); ++i)
result.push_back(rightResult[i]);
return result;
}
};
```
2. 循环解法
稍复杂点，大小集合都是8ms过

```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector result;

vector trace;
TreeNode *cur = root;
TreeNode *pre = NULL;
bool forward = true;
while(cur)
{
if (forward)
{
//have unvisited left
if (cur->left && pre != cur->left)
{
pre = cur;
trace.push_back(cur);
cur = cur->left;
continue;
}
forward = false;
}
else
{
//not return from right, add self
if(cur->right == NULL || cur->right != pre)
result.push_back(cur->val);
//go right if could
if(cur->right && pre != cur->right)
{
forward = true;
pre = cur;
trace.push_back(cur);
cur = cur->right;
continue;
}
//go up
pre = cur;
if (trace.size() > 0)
{
cur = trace[trace.size() - 1];
trace.pop_back();
} else
cur = NULL;

}
}

return result;
}
};
```
3. 循环解法，2012年12月6日重写，比上一个简洁
```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
if(NULL == root) return ret;

bool forward = true;
stack trace;
TreeNode *preNode = NULL;
trace.push(root);

while(trace.size()) {
TreeNode *curNode = trace.top();
if(forward) {
if(curNode->left && preNode != curNode->left) {
trace.push(curNode->left);
} else {
//no left or left visited
forward = false;
}
} else {
//backward, find sibling(right child)
//if not back from right child, then visit it
if(curNode->right != preNode)
ret.push_back(curNode->val);
if(curNode->right && preNode != curNode->right) {
//if have an unvisited right child, traval it.
trace.push(curNode->right);
forward = true;
} else {
//all sub-tree of this node is visited
trace.pop();
}
}
preNode = curNode;
}

return ret;
}
};
```