以递归的方式实现二叉树的中序遍历
时间: 2023-07-16 09:12:42 浏览: 41
递归方式实现二叉树的中序遍历,可以按照以下步骤进行:
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 inorderTraversal(root: TreeNode) -> List[int]:
res = []
if not root:
return res
def traverse(node):
if node.left:
traverse(node.left)
res.append(node.val)
if node.right:
traverse(node.right)
traverse(root)
return res
```
其中,函数 `inorderTraversal` 接收一个二叉树的根节点 `root`,返回一个列表,表示中序遍历的结果。
函数中定义了一个内部函数 `traverse`,它接收一个节点 `node`,按照上述步骤递归遍历左子树、访问当前节点和递归遍历右子树。在访问当前节点时,将节点的值添加到结果列表 `res` 中。
最后,调用 `traverse(root)` 开始递归遍历,并返回结果列表 `res`。