二叉树中序遍历非递归
时间: 2023-06-30 15:23:17 浏览: 98
二叉树的中序遍历非递归实现需要使用栈来实现,具体步骤如下:
1. 新建一个栈和一个指针变量p,初始时p指向根节点,栈为空。
2. 循环执行以下步骤,直到栈为空且p为空:
a. 如果p不为空,则将p入栈,并将p指向其左子节点。
b. 如果p为空,则将栈顶元素出栈并输出,然后将p指向栈顶元素的右子节点。
下面是该算法的Python实现代码:
```python
def inorderTraversal(root):
stack = []
p = root
while stack or p:
if p:
stack.append(p)
p = p.left
else:
node = stack.pop()
print(node.val)
p = node.right
```
其中,root为二叉树的根节点,val是节点的值。该算法的时间复杂度为O(n),空间复杂度为O(h),其中h为二叉树的高度。
相关问题
二叉树中序遍历非递归实现
二叉树的中序遍历是按照「左-根-右」的顺序遍历二叉树的节点。非递归实现可以使用栈来模拟递归的过程。具体来说:
1. 创建一个空栈,并将根节点入栈。
2. 只要栈不为空,就执行以下操作:
a. 将当前节点移动到左子树,并将左子树的根节点入栈,重复此操作直到当前节点为空。
b. 当前节点为空时,说明已经遍历完了当前节点的左子树,将栈顶元素出栈,访问该节点,并将当前节点移动到右子树。
c. 重复步骤2a和2b直到栈为空。
代码实现如下:
```
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* curr = root;
while (curr != nullptr || !s.empty()) {
while (curr != nullptr) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
cout << curr->val << " ";
curr = curr->right;
}
}
```
二叉树中序遍历非递归
二叉树中序遍历非递归算法可以使用栈来实现。具体实现方法如下:
1. 定义一个栈和一个指向根节点的指针。
2. 将根节点和它的所有左子树全部入栈。
3. 当栈不为空时,取出栈顶元素,将其值存入结果数组中。
4. 如果该节点有右子树,则将右子树及其所有左子树全部入栈。
5. 重复步骤3和4,直到栈为空。
代码实现如下(C++):
```
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* p = root;
while (p != NULL || !st.empty()) {
while (p != NULL) {
st.push(p);
p = p->left;
}
p = st.top();
st.pop();
res.push_back(p->val);
p = p->right; }
return res;
}
```
阅读全文