112. 路径总和

根结点到叶子结点的路径上值的和 ：在叶子结点上判断。

方法一：递归 DFS

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:return False
        if not root.left and not root.right: # 叶子结点
            return root.val == targetSum
        # 问题转化为左右子树递归
        return self.hasPathSum(root.right, targetSum - root.val) or self.hasPathSum(root.left, targetSum - root.val) 

方法二：广度优先搜索 BFS

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root: return False
        q = deque([(root, root.val)]) # 通过元组携带前缀和
        # q = [(root, root.val)] # DFS
        while q:
            cur, tem = q.popleft()
            # cur, tem = q.pop()
            if not cur.left and not cur.right: # 叶子结点
                if tem == targetSum: return True
                continue
                
            cur.left and q.append((cur.left, cur.left.val + tem))  
            cur.right and q.append((cur.right, cur.right.val + tem))      
        
        return False

113. 路径总和 II

方法一：DFS

cclaclass Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        
        def dfs(cur, tmp):
            path.append(cur.val)
            tmp -= cur.val
            if not tmp and not cur.left and not cur.right:
                res.append(path[:]) # copy
            
            cur.left and dfs(cur.left, tmp)
            cur.right and dfs(cur.right, tmp)
            path.pop()  # 回溯

        if not root: return []
        res, path = [], []
        dfs(root, targetSum)

        return res

方法二：广度优先搜索

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root: return [] 
        res = []
        q = deque([(root, [], targetSum)])  # 结点，路径，路径和 bfs
        # q = [(root, [], targetSum)]  # dfs

        while q:
            cur, path, tmp = q.popleft() # bfs
            # cur, path, tmp = q.pop() # dfs
            # path += [cur.val]
            # path.append(cur.val) # 列表 +=，append 对象不变 ！！！ 
            path = path + [cur.val] # 对象变了，不再需要 copy path 以及回溯
            tmp -= cur.val
            # 如果是叶子节点，同时和为零。
            if not cur.left and not cur.right and not tmp: 
                    res.append(path) # 保存路径

            cur.left and q.append((cur.left, path, tmp))
            cur.right and q.append((cur.right, path, tmp))

        return res

437. 路径总和 III

方法一：深度优先搜索

统计以每个结点为「路径开头」的所有合法路径。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        
        # def dfs(cur, tmp):
        #     if not cur: return 0            
        #     tmp -= cur.val             
        #     return dfs(cur.left, tmp) + dfs(cur.right, tmp) + (0 if tmp else 1)

        # if not root: return 0
        # return dfs(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)

        def dfs(cur, tmp): 
            return dfs(cur.left, tmp - cur.val) + dfs(cur.right, tmp - cur.val) + (0 if tmp != cur.val else 1) if cur else 0

        return dfs(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum) if root else 0

方法二: 前缀和

统计以每个结点为「路径结尾」的所有合法路径，即从根结点到当前结点的唯一路径中找有多少个结点的路径总和为 targetSum。

统计 sum[y] - sum[x] = targetSum 的数量，其中 x 始结点，y 尾结点 ，即 sum[x] = sum[y] - targetSum，统计 x 数量。
为了更快速的找到某个数值在路径中是否出现过，可以使用哈希表记录路径中每个数值出现的次数。
另外，为了处理包含根节点的情况，需要在哈希表中存储一个 (0,1) 的键值对。而且，并不需要一开始就把前缀和树计算出来，可以边遍历边计算，这里使用回溯来处理，因此这个点已经统计过了，防止影响树的其他分支的数量统计。

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        prefix = collections.defaultdict(int) # 记录路径中某个前缀和 : 出现的次数
        prefix[0] = 1 # 根节点前，前缀和为 0

        def dfs(cur, tmp):
            if not cur:  return 0            

            tmp += cur.val # 当前结点的前缀和
            res = prefix[tmp - targetSum] # 相当于找路径的起点，tmp - 起点的前缀和 = targetSum，即 tmp - targetSum 起点的前缀和。
            prefix[tmp] += 1 # 将当前前缀和个数记录下来
            res += dfs(cur.left, tmp) + dfs(cur.right, tmp)
            prefix[tmp] -= 1 # 回溯

            return res

        return dfs(root, 0)

方法三: 翻转列表的前缀和

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        def f(cur, prefix):
            if not cur: return 0
            prefix = [e + cur.val for e in prefix] + [cur.val]
            return prefix.count(targetSum) + f(cur.left, prefix) + f(cur.right, prefix)
            
            # tmp =  tmp + [cur.val]
            # prefix = list(accumulate(tmp[::-1]))
            # return prefix.count(targetSum) + f(cur.left, tmp) + f(cur.right, tmp)

        return f(root, [])

430. 扁平化多级双向链表

方法一：深度优先搜索

当遍历到某个节点 node 时，如果它的 child 成员不为空，就要先去处理 child 指向的链表结构，这就是一个「深度优先搜索」的过程。当完成了对 child 指向的链表结构的扁平化之后，就可以「回溯」到 node 节点。

为了能够将扁平化的链表插入 node 与 node 的下一个节点之间，需要知道扁平化的链表的最后一个节点 last，随后进行如下的三步操作：

将 node 与 node 的下一个节点 next 断开：
将 node 与 child 相连；
将 last 与 next 相连。

这样一来，就可以将扁平化的链表成功地插入。

在深度优先搜索完成后，返回给定的首节点即可。

需要注意的是，node.next 为空。此时，只需进行第二步操作。

此外，在插入扁平化的链表后，需要将 node 的 child 成员置为空。

class Solution:
    def flatten(self, head: "Node") -> "Node":
        def dfs(node: "Node") -> "Node":
            cur = node            
            last = None # 记录链表的最后一个节点

            while cur:
                nxt = cur.next
                # 如果有子节点，那么首先处理子节点
                if cur.child:
                    child_last = dfs(cur.child)
                    
                    nxt = cur.next
                    # 将 node 与 child 相连
                    cur.next = cur.child
                    cur.child.prev = cur

                    # 如果 nxt 不为空，就将 last 与 nxt 相连
                    if nxt:
                        child_last.next = nxt
                        nxt.prev = child_last

                    # 将 child 置为空
                    cur.child = None
                    last = child_last
                else:
                    last = cur
                cur = nxt

            return last

        dfs(head)
        return head

方法二：栈

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        q = []
        cur = head
        while cur or q:
            if cur.child:
                if cur.next: q.append(cur.next) 
                cur.child.prev = cur
                cur.next = cur.child
                cur.child = None

            if q and not cur.next:
                node = q.pop()
                cur.next = node
                node.prev = cur

            cur = cur.next
        return head