# [leetcode] Binary Tree Inorder Traversal

### Binary Tree Inorder Traversal

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.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.Here’s an example:

```   1
/ \
2   3
/
4
\
5
```

The above binary tree is serialized as `"{1,2,3,#,#,4,#,#,5}"`.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
stack<TreeNode *> s;
vector<int> inorderTraversal(TreeNode *root) {
vector<int> re;
if(root == NULL){
return re;
}
s.push(root);
while(!s.empty()){
TreeNode * p = s.top();
s.pop();
if(p->right != NULL){
s.push(p->right);
}
if(p->right == NULL && p->left == NULL){
re.push_back(p->val);
}
else{
s.push(p);
}
if(p->left != NULL){
s.push(p->left);
}
p->right = p->left = NULL; // WARNING: this will change the structure of original tree
}
return re;
}
};```

1. 给定一个节点p，如果该节点有左节点，则把该节点压入栈中，移动p至左节点，重复此操作；

2. 此时，p没有左节点，把p的val压入结果数组中。

3. 如果p的右节点为空，则栈顶元素出栈，赋给p，把p的val压入结果数组。重复步骤3

4. 如果p的右节点非空，p=p->right，跳至步骤1.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
stack<TreeNode *> s;
vector<int> inorderTraversal(TreeNode *root) {
vector<int> re;
if(root == NULL){
return re;
}
TreeNode * p = root;
while(p != NULL || !s.empty()){
if(p != NULL){
while(p->left != NULL){
s.push(p);
p = p->left;
}
re.push_back(p->val);
p = p->right;
}
else{//p is NULL
p = s.top();
s.pop();
re.push_back(p->val);
p = p->right;
}
}
return re;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.