当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 中序遍历二叉树-----迭代方式

中序遍历二叉树-----迭代方式

2018年02月05日  | 移动技术网IT编程  | 我要评论

巢邦网,dnf进入舰长室,一年级语文上册教案

LintCode-67 中序遍历二叉树并返回遍历数组

 1 #include <vector>
 2 #include <stack>
 3 
 4 using std::vector;
 5 using std::stack;
 6 
 7 struct TreeNode
 8 {
 9      int val;
10     TreeNode *left, *right;
11     TreeNode(int x):val(x), left(0), right(0){}
12 };
13 
14 class Solution
15 {
16 public:
17     vector<int>  inorderTraversal(TreeNode *root)
18     {
19         vector<int> result;
20         stack<TreeNode*> st;
21         TreeNode *p = root;
22     
23         while(p || !st.empty())
24         {
25             while(p)  //将二叉树左结点全部入栈
26             {
27                 st.push(p);
28                 p = p->left;
29             }
30             p = st.top(); //取出栈顶结点，即二叉树最左结点
31             st.pop();
32             result.push_back(p->val);
33             p = p->right; //同样方式遍历结点右树
34         }
　　　　　　return result;
35     }
36 };

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网