欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-29 11:58:28
LintCode-67 中序遍历二叉树并返回遍历数组 ......

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 };