二叉树深度优先遍历
时间: 2023-07-18 22:07:12 浏览: 43
二叉树的深度优先遍历有三种方式:前序遍历、中序遍历和后序遍历。
前序遍历的遍历顺序是:根节点 -> 左子树 -> 右子树。
中序遍历的遍历顺序是:左子树 -> 根节点 -> 右子树。
后序遍历的遍历顺序是:左子树 -> 右子树 -> 根节点。
下面是使用递归实现前、中、后序遍历的示例代码:
```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 []
res = []
res.append(root.val) # 将根节点加入结果列表
res += preorderTraversal(root.left) # 遍历左子树
res += preorderTraversal(root.right) # 遍历右子树
return res
# 中序遍历
def inorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = []
res += inorderTraversal(root.left) # 遍历左子树
res.append(root.val) # 将根节点加入结果列表
res += inorderTraversal(root.right) # 遍历右子树
return res
# 后序遍历
def postorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = []
res += postorderTraversal(root.left) # 遍历左子树
res += postorderTraversal(root.right) # 遍历右子树
res.append(root.val) # 将根节点加入结果列表
return res
```
这里假设二叉树的节点是一个类对象,类中包含节点值、左子节点和右子节点。以上三个遍历函数都接收一个根节点作为参数,返回一个列表,其中包含了按照对应顺序遍历得到的节点值。