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

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