二叉树的四种遍历

本文最后更新于:6 天前

二叉树的四种遍历

对于一个给定的二叉树,有四种遍历方式:先序遍历、中序遍历、后序遍历、层次遍历。

  • 前序遍历:根节点 -> 左孩子 -> 右孩子,遍历结果为 1 2 4 5 3 6 7
  • 中序遍历:左孩子 -> 根节点 -> 右孩子,遍历结果为 4 2 5 1 6 3 7
  • 后序遍历:左孩子 -> 右孩子 -> 根节点,遍历结果为 4 5 2 6 7 3 1
  • 层序遍历:按照每一层从左向右的方式进行遍历,遍历结果为 1 2 3 4 5 6 7

1 前序遍历

144. 二叉树的前序遍历

复杂度分析

  • 时间复杂度:O(n),n 为节点数,访问每个节点恰好一次。

  • 空间复杂度:O(h),h 为树的高度。最坏情况下需要空间 O(n),平均情况为 O(logn)。

1
2
3
4
5
6
7
8
9
10
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def pre_order(root):
if root:
res.append(root.val)
pre_order(root.left)
pre_order(root.right)
res = []
pre_order(root)
return res

2 中序遍历

94. 二叉树的中序遍历

复杂度分析

  • 时间复杂度:O(n),n 为节点数,访问每个节点恰好一次。

  • 空间复杂度:O(h),h 为树的高度。最坏情况下需要空间 O(n),平均情况为 O(logn)。

1
2
3
4
5
6
7
8
9
10
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
def in_order(root):
if root:
in_order(root.left)
res.append(root.val)
in_order(root.right)
res = []
in_order(root)
return res

3 后序遍历

145. 二叉树的后序遍历

复杂度分析

  • 时间复杂度:O(n),n 为节点数,访问每个节点恰好一次。

  • 空间复杂度:O(h),h 为树的高度。最坏情况下需要空间 O(n),平均情况为 O(logn)。

1
2
3
4
5
6
7
8
9
10
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def post_order(root):
if root:
post_order(root.left)
post_order(root.right)
res.append(root.val)
res = []
post_order(root)
return res

4 层序遍历

102. 二叉树的层序遍历

复杂度分析

  • 时间复杂度:O(n),n 为节点数,访问每个节点恰好一次。

  • 空间复杂度:O(h),h 为树的高度。最坏情况下需要空间 O(n),平均情况为 O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
queue = collections.deque()
queue.append(root)
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!