102. 二叉树的层次遍历 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

解：

利用队列实现bfs，从根节点开始入队，如果左右子树不空，就入队。把每层的所有节点都遍历完了，下一层的最左节点再出队。（用for循环控制即可，因为在开始遍历新的一层之前，queue中只存了这一层的全部节点，batch process）。O(N)

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

import collections
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []

    queue = collections.deque()  
    queue.append(root)

    # visited = set(root)  # 图的 bfs 需要 visited 标志

    res = \[\]  
    while queue:  
        current\_level = \[\]  
        level\_size = len(queue)

        for \_ in range(level\_size):  
            node = queue.popleft()  
            current\_level.append(node.val)  
            if node.left:  
                queue.append(node.left)  
            if node.right:  
                queue.append(node.right)

        res.append(current\_level)  
    return res

dfs解决，开拓一下思路，递归的不断把level放下去，就把dfs遍历到的每个节点按level灌到res里面即可。

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []

    def dfs(node, level):  
        if not node:  
            return  
        if len(res) - 1 < level:  # res最后一行的索引比当前行的索引还小，说明当前行还没有进行任何遍历，放一个空list在res最后  
            res.append(\[\])

        res\[level\].append(node.val)  # 把node放到对应行去  
        dfs(node.left, level+1)  # 遍历node的左右孩子  
        dfs(node.right, level+1)

    dfs(root, 0)  
    return res

104. 二叉树的最大深度 https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

解：

最直接的思路就是分治，递归实现，每个节点的深度为max(left, right) +1。

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

bfs，第一个出现的叶子结点所在的层是深度最小的，最后一个节点所在的层深度最大。

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
queue = [root]
max_depth = 0
while queue:
level_size = len(queue)
if level_size:
max_depth += 1
for _ in range(level_size):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return max_depth

dfs，从根节点开始按深度遍历，递归中按level向下，如果当前节点的level大于最大深度，最大深度就+1。

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0

    max\_depth = 1 # 根节点不空，至少为1  
    def dfs(node, level):  
        nonlocal max\_depth  
        if not node:  
            return  
        if max\_depth < level:  
            max\_depth += 1  
        dfs(node.left, level+1)  
        dfs(node.right, level+1)  
    dfs(root, 1)  
    return max\_depth

111. 二叉树的最小深度 https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

解：

分治，如果root左子树为空，最小深度就是右子树的最小深度+1；如果右子树为空，最小深度为左子树最小深度+1；如果左右都不空，分别找到最小深度，整体的最小深度为更小的深度+1

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left:
return self.minDepth(root.right) + 1
if not root.right:
return self.minDepth(root.left) + 1

    # 分治  
    left = self.minDepth(root.left)  
    right = self.minDepth(root.right)

    return min(left, right) + 1  # 聚合子问题的结果

bfs，一层一层向下扩展，第一个出现的叶子结点深度最小

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
queue = [root]
level = 0
while queue:
level_size = len(queue)
if level_size:
level += 1
for _ in range(level_size):
node = queue.pop(0)
if not node.left and not node.right: # 第一个叶子结点的深度最小
return level
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return level

dfs

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

import sys
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0

    min\_depth = sys.maxsize  
    def dfs(node, level):  
        nonlocal min\_depth  
        if not node:  
            return  
        if node.left is None and node.right is None:  # node 是叶子节点  
            if level < min\_depth:  
                min\_depth = level  
                return

        dfs(node.left, level+1)  
        dfs(node.right, level+1)

    dfs(root, 1)  
    return min\_depth

22. 括号生成 https://leetcode-cn.com/problems/generate-parentheses/

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

解：

dfs + 剪枝，局部不合法，不再递归；左右括号都只能有n个；先加左括号；已经产生的序列中，左括号个数一定大于右括号的情况下，才能加右括号

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n <= 0:
return []

    res = \[\]  
    def dfs(left, right, n, result):   # 已用左括号个数，已用右括号个数，n，当前产生的括号序列  
        nonlocal res  
        if left == n and right == n:  
            res.append(result)  
            return

        if left < n:  
            dfs(left+1, right, n, result+'(')

        if left > right and right < n:  
            dfs(left, right+1, n, result+')')

    dfs(0, 0, n, '')  
    return res

46. 全排列 https://leetcode-cn.com/problems/permutations/

给定一个没有重复数字的序列，返回其所有可能的全排列。

解：

回溯，选第一个数，然后选剩下可选的数。

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return[[]]

    ans = \[\]

    def backtrack(nums, track):  
        nonlocal ans  
        if not nums:  
            ans.append(track)  
        else:  
            for i in range(len(nums)):  
                # track加入当前选的nums\[i\], 下一层nums\[i\]也不能选了  
                backtrack(nums\[:i\]+nums\[i+1:\], track+\[nums\[i\]\])  
                # track自然的回退了，因为没有真的append上去

    backtrack(nums, \[\])  
    return ans

回退用交换来实现。

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return[[]]

    ans = \[\]  
    n = len(nums)

    def backtrack(first):  
        nonlocal ans  
        if first == n:  
            ans.append(nums\[:\])  
        else:  
            for i in range(first, n):  
                nums\[first\], nums\[i\] = nums\[i\], nums\[first\]  # 选第i个数加入解，把选择的数放nums最前面，因为原本在i之前的数下一轮是可以被选择的  
                backtrack(first+1)  
                nums\[first\], nums\[i\] = nums\[i\], nums\[first\]  # 回退

    backtrack(0)  
    return ans

78. 子集 https://leetcode-cn.com/problems/subsets/

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

解：

还是典型的回溯，不过因为是记录子集，每次track都记录一下就行了。

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
def backtrack(nums, track):
nonlocal ans
ans.append(track)
for i in range(len(nums)):
backtrack(nums[i+1:], track+[nums[i]])
backtrack(nums, [])
return ans

或者直接迭代求解，这里设计的比较巧妙。每来一个新的数，就加到ans的中每个解中去，然后把新的ans和没加之前的ans合并。

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = [[]]
for i in nums:
ans += [[i] + pre_solution for pre_solution in ans]
return ans

17. 电话号码的字母组合 https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解：

dfs，每个数字对应的可选择字符可以用哈希表先存好。按照dfs的框架

for c in choices:

　　# choose and add to track

　　dfs(nums, track)

　　# unchoose

class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
words = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
res = []
n = len(digits)

    def dfs(i, track):  
        nonlocal res  
        if i == n:  
            res.append(track)  
            return  
        else:  
            for choice in words\[digits\[i\]\]:  
                dfs(i+1, track+choice)  
    dfs(0, '')  
    return res