遍历：DFS/回溯

问题一（统计个数）：下属个数

Organization and Employee hierarchy tree view | Odoo

在一家公司中，我们需要知道每个员工有几个下属。那么我们给每一个员工一个分数Score：如果TA没有下级，那么Score=1，否则Score=下级的个数+1（自身）。我们把每一个员工看成一个节点，那么这个公司从CEO开始作为根节点就可以看作是一棵树。

那么问题来了：给定一个公司结构和员工号，我们如何查找TA的score？这样的问题一般用DFS来递归解决。

一次求解

def dfs(graph, id):
    if id not in graph: return 0 # base case
    score = 1                    # 自己
    for e in graph[id]:          # 下属
        score += dfs(graph, e)
    return score

带Cache的求解

DFS搜索经常出现的问题就是重复查询。比如说在这个问题中，我们两次分别查询员工与TA的老板，那么员工的score就是可以重复利用的信息。对于这样的重复子问题，有两种解决方案：

• 备忘录：在自顶向下递归的最外面加一个cache（或者memo）来存储已经求解了的答案。在动态规划的介绍中我们再重温这个话题。

• 动态规划：利用子问题的结构，用自底向上的方法来消灭重复查询。比如练习《验证平衡二叉树》，不像动态规划，然而用了这样的思路。

讨论：如果面对多次查找的同时，对树的结构还可能有改变（公司变动）。那么我们需要灵活改变cache(cache invalidation)来应对。比如我们可以拓展cache来存储以下内容cache: id -> score, manager_id, set(report_id)

这样一来，我们相当于拥有了对父节点（老板）的指针。一旦有一个subtree（部门）有改变，我们就可以向上遍历，来改动他们在cache中的score。

问题二（求解）：迷宫出口

给定一张迷宫，入口entrance与出口exit，如何从entrance到达exit？有两个方便的函数来我们进行选择和判断：

• neighbors(p)来访问从p出发相邻的点

• wall(p,q)来判断每个两点p与q之间是否隔着一堵墙

从起点出发进行搜索，而且我们的在每一个点的策略是，每次遇到选择就选择第一个可行解（neighbors(p)当中给我们的第一个结果，可以是向左转前进一格）。直到我们没有选择了再回头。如果有解（exit可到达），那么至少有一条路径是连接出入口的，我们把它记下来。

注意这里“第一个可行解“可能会排除以下选择：

• 已经走过的路：一般用path（走过的路径）或者vis（额外的标记数组）来标记

• 走不通的路：越界、隔着墙等不符合最后答案的选择。

这道题里neighbors(p)帮我们做选择，wall(p,q)帮我们排除不合法选择。

回溯

def dfs(path, p):
    if p==exit:
        res.append(path)
        return
    for q in neighbors(s):
        if q in path: continue  # visited
        if wall(p, q): continue # it's a wall
        path.append(q)          # 探索
        dfs(path, q)
        path.pop()              # 回溯

res = []
dfs([enter], enter)
return res

非回溯

在Python中有一个偷懒的解法。在上面非回溯解法中，我们+(__iadd__operator)来创造一个新的list。新的list（也需要新的空间）会来替我们搜索，就不需要回溯了。

可行解与所有解：有的时候我们不需要找到所有可行解，而是只需找到任意可行解。那么我们早早的就可以退出递归函数。

def dfs(path, p):
    if p==exit:
        res[:] = path
        return True
    for q in neighbors(s):
        if q in path: continue  # visited
        if wall(p, q): continue # it's a wall
        path.append(q)          # 探索
        if dfs(path, q):
            return True         # 找到可行解！
        path.pop()              # 回溯
    return False                # 没有可行解

res = []
dfs([enter], enter)
return res

验证平衡二叉树

“一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。“

这是一道简单题，然而有两种复杂度截然不同的解法。参考代码:

O(N)的自底向上算法

def isBalanced(root):
    def height(root):
        if not root: return 0
        left = height(root.left)
        right = height(root.right)
        if left==-1 or right==-1 or \
           abs(left-right) > 1:
            return -1
        return max(left, right) + 1

    return height(root) != -1

O(N^2)的自上向下算法

子集/排列

• 子集（Subsets）： $2^N$ 个幂集

• 子集 II（SubsetsUnique）：去重的幂集

• 全排列（Permute）: $n!$ 个排列

• 全排列 II（PermuteUnique）：去重的全排列

• 组合（Combine）： $\frac{n!}{k!(n-k)!}$ 个顺序无关的放球问题

• 组合总和（CombineSum）：每个元素可以取无限次，记得剪枝。方案数可以用完全背包DP解决。

• 组合总和II（CombineSumUnique）：每个元素最多可以取1次，枚举 $2^N$ 个子集记得剪枝。方案数可以用0-1背包DP解决。

Subsets

输入：nums = [1,2,3]
输出：
[[],
[1],
[2],
[1,2],
[3],
[1,3],
[2,3],
[1,2,3]]

# iteration with state
n = len(nums)
res = []
for i in range(1<<n):
    res.append([nums[j] for j in range(n) if (i>>j)&1])
return res

# recursion
def dfs(path, i):
    res.append(path)
    for j in range(i, len(nums)):
        dfs(path+[nums[j]], j+1)

res = []
dfs([], 0)
return res

SubsetsUnique

Permute

PermuteUnique

Combine

CombineSum

CombineSumUnique