二叉树的中序遍历顺序实现
时间: 2023-10-30 14:10:21 浏览: 40
二叉树的中序遍历顺序是指先遍历左子树,然后访问根节点,最后遍历右子树。
中序遍历可以使用递归或者迭代的方法实现。以下是递归实现的示例代码:
```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:
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
```
以下是迭代实现的示例代码:
```python
def inorderTraversal(root: TreeNode) -> List[int]:
res = []
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
return res
```
以上两种实现方式都是时间复杂度为 O(n),其中 n 是二叉树的节点数。递归实现方式需要使用系统栈,因此空间复杂度为 O(n)。迭代实现方式使用了一个辅助栈,因此空间复杂度为 O(h),其中 h 是二叉树的高度。