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

2018-02-04 18:33:14来源:cnblogs.com作者:cppthomas人点击

分享

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

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台