二叉树中和为某一值的路径（Python and C++解法）

题目：

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

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

5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
返回:

[
[5,4,11,2],
[5,8,4,5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof

思路：

　　路径肯定包括根节点，因此遍历节点时应该保证先遍历根节点，前序遍历符合要求。

　　需要有列表记录下遍历过的路径。

　　Python中赋值语句总是建立对象的引用值，而不是复制对象,所以如果直接res.append(path)，当后面改变path内容时，res里的path会随之改变，因此可以使用浅拷贝，复制一个对象，方法如path[:]，或list(path)

Python解法：

 1 class TreeNode:
 2     def __init__(self, x):
 3         self.val = x
 4         self.left = None
 5         self.right = None
 6 
 7 
 8 class Solution:
 9     def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
10         res = []  # 存储所有正确的路径
11         path = []  # 存储当前路径
12 
13         def dfs(fatherNode, sumPath):
14             if fatherNode == None:  # 递归终止条件
15                 return
16             path.append(fatherNode.val)  # 每条路径都有根节点
17             sumPath -= fatherNode.val
18             # 路径满足的条件是sum减为零，且已到达叶节点
19             if sumPath == 0 and fatherNode.left == None and fatherNode.right == None:
20                 res.append(list(path))
21             dfs(fatherNode.left, sumPath)  # 递归判断左子树是否有符合的路径
22             dfs(fatherNode.right, sumPath)  # 递归判断右子树是否有符合的路径
23             # 如果到某一叶节点的路径不符合要求，那么应return回溯到上一层，删除该叶节点，sum也随着回溯处于上一层的数值
24             path.pop()  # 当前的函数结束后才能pop叶节点
25         dfs(root, sum)  # 函数调用
26         return res

C++解法：

 1 struct TreeNode {
 2     int val;
 3     TreeNode *left;
 4     TreeNode *right;
 5     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 6 };
 7 
 8 class Solution {
 9 public:
10     vector<vector<int>> res;  // 存储最终结果
11     vector<int> path;
12     vector<vector<int>> pathSum(TreeNode* root, int sum) {
13         dfs(root, sum);
14         return res;
15     }
16 
17     void dfs(TreeNode *root, int sum) {
18         if (root == NULL)    return;  // 递归终止条件
19         path.push_back(root->val);  // 路径肯定要添加进根节点
20         sum -= root->val;
21         // 路径满足的条件是sum减为零，且已到达叶节点
22         if (sum == 0 && root->left == NULL && root->right == NULL)
23             res.push_back(path);
24         dfs(root->left, sum);  // 递归判断左子树是否有符合的路径
25         dfs(root->right, sum);  // 递归判断右子树是否有符合的路径
26         // 如果到某一叶节点的路径不符合要求，那么应return回溯到上一层，删除该叶节点，sum也随着回溯处于上一层的数值
27         path.pop_back();  // 当前的函数结束后才能pop叶节点
28     }
29 };