中序遍历二叉树-----迭代方式
程序员文章站
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 };
上一篇: 浅谈2016互联网隐私安全需要注意什么
下一篇: 周鸿祎的第一次创业失败