剑指offer 面试题34. 二叉树中和为某一值的路径（中）& LeetCode 113. 路径总和 II（中）

典型的二叉树深度优先遍历的应用

Question

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例：给定如下二叉树，以及目标和 sum = 22， 

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
返回： 
1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]
提示：节点总数 <= 10000

测试用例

功能测试（二叉树中有一条、多条符合要求的路径；二叉树中没有符合要求的路径）。 特殊输入测试（指向二叉树根节点的指针为nullptr指针）。

本题考点

考查应聘者分析复杂问题的思维能力。应聘者遇到这个问题的时候，如果一下子没有思路，则不妨从一个具体的例子开始，一步步分析路径上包含哪些节点，这样就能找出其中的规律，从而想到解决方案。 考查应聘者对二叉树的前序遍历的理解。

Intuition

典型的二叉树深度优先遍历的应用

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def pathSum(self, root: TreeNode, _sum: int) -> List[List[int]]:
        if root == None:  return []
        def _dfs(path=[], root=root):
            if root.left == root.right == None and sum(path + [root.val]) == _sum:
                res.append(path[:] + [root.val])
                return
            if root.left:
                _dfs(path + [root.val], root.left)
            if root.right:
                _dfs(path + [root.val], root.right)

        res = []
        _dfs()

        return res