94. Binary Tree Inorder Traversal
提交地址: https://leetcode.com/problems/binary-tree-inorder-traversal/
Total Accepted: 121442 Total Submissions: 306788 Difficulty: Medium
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? .
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}"
.
分析: 借助栈实现非递归中序遍历算法的方法如下: 1)将二叉树的根结点作为当前结点。 2)若当前结点非空,则该结点进栈并将其左孩子结点作为当前结点,重复步骤2),直到当前结点为NULL为止。 3)若栈非空,则将栈顶结点出栈并作为当前结点,接着访问当前结点,再将当前结点的右孩于结点作为当前结点。 4)重复步骤2)、3),直到栈为空且当前结点为NULL为止。
AC代码:
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x): val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> res;
TreeNode *p;
stack<TreeNode*> s;
p=root;
while(!s.empty() || p!=NULL)
{
if(p != NULL)
{
s.push(p); // 未到叶结点,持续往左孩子方向深处遍历
p=p->left; // 将左结点作为当前结点
}
if(p == NULL) { // 此时栈非空,当前结点为NULL,让刚入栈的结点出栈
p=s.top();
res.push_back(p->val); // 删除前先保存
s.pop();
p=p->right; // 将右结点作为当前结点
}
}
return res; // 栈空且到最远右结点时结束
}
};
// 以下为测试部分
/*
int main()
{
Solution sol;
vector<int> res;
TreeNode *root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
res=sol.inorderTraversal(root);
for(int i:res)
cout<<i<<" "; // 此处为vector遍历的方法,C++11标准支持
return 0;
}
*/