DFS、BFS

算法

一、DFS

104. 二叉树的最大深度

  1. 代码:
1
2
3
4
def maxDepth(self, root: Optional[TreeNode]) -> int:
	if root is None:
		return 0
	return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

二、BFS

0. 提示

  1. 若需要按层区分: `while len(q)>0 的条件内部需要 for _ in range(len(q))

102. 二叉树的层序遍历

  1. 题意: 需要按层区分的 BFS
  2. 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    result = []
    if root is None:
        return result
    q = deque()
    q.append(root)
    while len(q)>0:
        layer = []
        for _ in range(len(q)):
            node = q.popleft()
            layer.append(node.val)
            if node.left is not None:
                q.append(node.left)
            if node.right is not None:
                q.append(node.right)
        result.append(layer)
    return result