写出二叉树的中序遍历算法
时间: 2023-07-26 22:44:30 浏览: 46
二叉树的中序遍历是指按照左子树、根节点、右子树的顺序遍历二叉树。中序遍历算法可以使用递归或者非递归方式实现。
以下是二叉树中序遍历的递归算法实现:
```python
def inorderTraversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def inorder(root):
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
inorder(root)
return res
```
以下是二叉树中序遍历的非递归算法实现,使用栈来辅助实现:
```python
def inorderTraversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
```
以上两种算法的时间复杂度均为 O(n),其中 n 表示二叉树中的节点数。