python可以用哪几种写法实现中序遍历
时间: 2023-10-09 11:12:52 浏览: 47
中序遍历是二叉树遍历的一种方式,可以使用递归和迭代两种方式实现。
递归实现:
```python
class TreeNode:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder_traversal(root: TreeNode):
if not root:
return
inorder_traversal(root.left)
print(root.value)
inorder_traversal(root.right)
```
迭代实现:
```python
def inorder_traversal(root: TreeNode):
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
print(node.value)
node = node.right
```
以上两种方式都可以实现中序遍历,其中递归实现简单易懂,但存在函数调用栈溢出的可能性,而迭代实现则使用了辅助栈,可以避免函数调用栈的溢出。
相关推荐
![](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)
![](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)
![](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)