# 【leetcode】Binary Tree Inorder Traversal

Question ：

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.

Anwser 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:
vector<int> inorderTraversal(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> result(0);

if (root == NULL)  return result;

stack<TreeNode *> S;
TreeNode* p = root;

do
{
if (p != NULL) {
S.push(p);
p = p->left;
} else {
p = S.top();
S.pop();

result.push_back(p->val);
p = p->right;
}
}while(!S.empty() || p != NULL);

return result;
}
};```

Anwser 2 ：

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

void dfs(TreeNode *p, vector<int> &result)
{
if(p->left != NULL)
dfs(p->left, result);

result.push_back(p->val);

if(p->right!=NULL)
dfs(p->right, result);
}

vector<int> inorderTraversal(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> result;
result.clear();

}

return result;
}
};```

Anwser 3 ：

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> result;
result.clear();
stack<TreeNode *> stack_in;
stack<TreeNode *> stack_out;

if(root == NULL) return result;

stack_in.push(root);
while(!stack_in.empty())
{
TreeNode *node_in = stack_in.top();
stack_in.pop();
stack_out.push(node_in);
if(node_in->right!=NULL && node_in->left!=NULL)
{
stack_in.push(node_in->right);
stack_in.push(node_in->left);
} else if(node_in->left!=NULL && node_in->right==NULL) {
stack_in.push(node_in->left);
} else if(node_in->left==NULL && node_in->right!=NULL) {
stack_in.push(node_in->right);
result.push_back(node_in->val);
stack_out.pop();
} else {
result.push_back(node_in->val);
stack_out.pop();
while(!stack_out.empty())
{
TreeNode * tmp = stack_out.top();
stack_out.pop();
result.push_back(tmp->val);
if(tmp->right!=NULL)
break;
}
}
}
return result;
}
};```

0 条评论

• ### Android中visibility属性

Android开发中，大部分控件都有visibility这个属性，其属性有3个分别为“visible ”、“invisible”、“gone”。主要用来设置控制...

• ### select,poll,epoll区别

select的本质是采用32个整数的32位，即32*32= 1024来标识，fd值为1-1024。当fd的值超过1024限制时，就必须修改FD_SETSIZE的...

• ### 【leetcode】Plus One

Given a number represented as an array of digits, plus one to the number.

• ### 波士顿动力机器人离下一次震惊世界还需要一点时间，搬箱子不成反摔倒

波士顿动力稍有动静就会引发轰动，这次也不例外。一段最新流出的视频显示了波士顿动力的Atlas机器人试着搬箱子然后放到架子上——尝试很久未果，最终无情倒下。此前业...

• ### 【允悲】波士顿动力机器人跪了！搬箱子不成反摔倒

【新智元导读】波士顿动力稍有动静就会引发轰动，这次也不例外。一段最新流出的视频显示了波士顿动力的Atlas机器人试着搬箱子然后放到架子上——尝试很久未果，最终无...

• ### Spring面试27道高频考点，你能答出几道？

Spring框架是一个为Java应用程序开发提供综合、广泛的基础性支持的Java平台。 Spring帮助开发者解决了开发中基础性的问题，使得开发人员可以专注于应...

• ### 27道高频Spring面试题，你能答对几个？

Spring框架是一个为Java应用程序开发提供综合、广泛的基础性支持的Java平台。 Spring帮助开发者解决了开发中基础性的问题，使得开发人员可以专注于应...

• ### Spring Cloud Gateway监控

只要为Spring Cloud Gateway添加Spring Boot Actuator（ spring-boot-starter-actuator ）的依赖...

• ### python队列Queue

Queue是python标准库中的线程安全的队列（FIFO）实现,提供了一个适用于多线程编程的先进先出的数据结构，即队列，用来在生产者和消费者线程之间的信息传递

• ### Spring框架的演变

如果想要解释Spring，那么最难的部分就是对其进行分类。通常情况下，Spring被描述为构建Java应用程序的轻量级框架，但这种描述带来了两个有趣的观点。