二叉树的中序遍历——迭代算法
程序员文章站
2022-06-17 19:54:24
...
题目
思路
中序遍历的思想是:左子树——根节点——右子树
所以相应的思路为:
- 不断寻找左子树根节点
- 当该左子树为空时,输出该节点
- 遍历右子树
相应代码如下:
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> s;
TreeNode* tre = root;
while (tre || !s.empty()) {
while (tre) {//不断寻找左节点
s.push(tre);
tre = tre->left;
}
//当左子树为空时,则将该节点从栈中弹出
tre = s.top();
s.pop();
v.push_back(tre->val);
tre = tre->right;//最后遍历右子树
}
return v;
}
};
上一篇: 栈实现中序遍历二叉树
下一篇: 抓取并解密HTTPS流量