7-1 二叉树的遍历
时间: 2023-11-28 13:04:09 浏览: 80
以下是二叉树的三种遍历方式的Python实现:
1. 先根遍历(先序遍历)
先访问根节点,再访问左子树,最后访问右子树。
```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
```
2. 中根遍历(中序遍历)
先访问左子树,再访问根节点,最后访问右子树。
```python
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
```
3. 后根遍历(后序遍历)
先访问左子树,再访问右子树,最后访问根节点。
```python
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
```