题解 | JZ84 二叉树中和为某一值的路径(三)
这道题可以分成两步，先遍历所有的节点，再在当前节点上，寻找路径。
按照这种方法不会重复，也不会遗漏。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
int ans = 0;
int FindPath(TreeNode* root, int sum) {
// write code here
if (!root) return 0;
FindPath2(root, sum, root->val);
if (root->left) FindPath(root->left, sum);
if (root->right) FindPath(root->right, sum);
return ans;
}
void FindPath2(TreeNode* root, int sum, int now) {
if (!root) return;
// int res = 0;
if (sum == now) ans++;
if (root->left) {
FindPath2(root->left, sum, now+root->left->val);
}
if (root->right) {
FindPath2(root->right, sum, now+root->right->val);
}
return ;
}
};
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @param sum int整型
# @return int整型
#
class Solution:
ans = 0
def FindPath(self , root: TreeNode, sum: int) -> int:
# write code here
if not root:
return 0
self.FindPath2(root, sum, root.val)
self.FindPath(root.left, sum)
self.FindPath(root.right, sum)
return self.ans
def FindPath2(self, root: TreeNode, sum: int, now: int):
if not root:
return
if sum == now:
self.ans += 1
if root.left:
self.FindPath2(root.left, sum, now + root.left.val)
if root.right:
self.FindPath2(root.right, sum, now + root.right.val)
return
