二叉树的遍历python
时间: 2023-10-14 12:25:47 浏览: 33
二叉树的遍历有三种方式:前序遍历、中序遍历和后序遍历。下面是它们的Python实现:
```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]:
res = []
def dfs(root):
if not root:
return
res.append(root.val)
dfs(root.left)
dfs(root.right)
dfs(root)
return res
# 中序遍历
def inorderTraversal(root: TreeNode) -> List[int]:
res = []
def dfs(root):
if not root:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res
# 后序遍历
def postorderTraversal(root: TreeNode) -> List[int]:
res = []
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
res.append(root.val)
dfs(root)
return res
```
其中,`TreeNode`是二叉树节点的定义。`preorderTraversal`、`inorderTraversal`和`postorderTraversal`分别是前序遍历、中序遍历和后序遍历的实现。这里使用了递归的方式实现遍历。