二叉树的非递归遍历py
时间: 2024-03-01 11:21:42 浏览: 45
二叉树的非递归遍历可以使用栈来实现。具体步骤如下:
1. 新建一个栈,将根节点入栈;
2. 循环执行以下步骤,直到栈为空:
1. 弹出栈顶节点并访问它;
2. 如果该节点有右子节点,则将右子节点入栈;
3. 如果该节点有左子节点,则将左子节点入栈。
下面是实现二叉树的前序、中序和后序遍历的非递归代码示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
def inorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
stack, res = [], []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
def postorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
stack1, stack2, res = [root], [], []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
res.append(stack2.pop().val)
return res
```
其中,前序遍历使用一个栈来存储未处理的节点,中序遍历使用两个栈来存储未处理的节点和已处理的节点,后序遍历也使用两个栈来存储未处理的节点和已处理的节点。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)