python 实现二叉树的中序遍历 详细解读
时间: 2023-12-01 13:27:23 浏览: 38
二叉树的中序遍历是指先访问二叉树的左子树,然后访问根节点,最后访问右子树,即左-根-右的访问顺序。下面是 Python 实现二叉树中序遍历的代码:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: TreeNode) -> List[int]:
res = []
inorder(root, res)
return res
def inorder(root: TreeNode, res: List[int]):
if root is None:
return
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
```
首先定义了一个 TreeNode 类,表示二叉树的节点,包含一个值 val 和左右子节点 left 和 right。
然后定义了一个 inorderTraversal 函数,该函数接收一个二叉树的根节点,并返回一个 List[int] 类型的结果。
最后定义了一个 inorder 函数,该函数用于实现中序遍历,接收当前节点和结果列表 res 作为参数。如果当前节点为空,直接返回;否则,先递归遍历左子树,将根节点的值添加到结果列表中,最后递归遍历右子树。
在 inorderTraversal 函数中,先创建一个空的结果列表 res,然后调用 inorder 函数进行遍历,并返回结果列表 res。
使用示例:
```
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root)) # [1, 3, 2]
```
以上就是 Python 实现二叉树中序遍历的详细解读。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)