二叉树的中序遍历顺序实现
时间: 2023-10-30 19:10:21 浏览: 42
二叉树的中序遍历顺序是指先遍历左子树,然后访问根节点,最后遍历右子树。
中序遍历可以使用递归或者迭代的方法实现。以下是递归实现的示例代码:
```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 是二叉树的高度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)