博文中会简要介绍Leetcode P0113题目分析及解题思路。
“Path Sum II”是p0112的变形题，本质上也是利用深度优先搜索。由于需要求从根结点到叶子结点的路径上所有值的和，解法上是本层依赖下层结果，所以这里采取递归回溯的方法。
一旦最后叶子结点的值加上前面路径上的所有值的和等于目标值，则记录这一路径即可。
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null)
return this.paths;
this.traverse(root, sum, 0, new ArrayList<>());
return this.paths;
}
private List<List<Integer>> paths = new ArrayList<>();
private void traverse(TreeNode curr, int target, int sum, List<Integer> path) {
if (curr.left == null && curr.right == null) {
if (sum+curr.val == target) {
path.add(curr.val);
this.paths.add(new ArrayList<>(path));
path.remove(path.size()-1);
}
}
path.add(curr.val);
if (curr.left != null)
this.traverse(curr.left, target, sum+curr.val, path);
if (curr.right != null)
this.traverse(curr.right, target, sum+curr.val, path);
path.remove(path.size()-1);
}
}
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if (!root)
return this->paths;
vector<int> path;
this->Dfs(root, sum, 0, path);
return this->paths;
}
private:
vector<vector<int>> paths;
void Dfs(TreeNode *curr, int target, int sum, vector<int> &path) {
if (!curr->left && !curr->right) {
if (sum+curr->val == target) {
path.push_back(curr->val);
this->paths.push_back(vector<int>(path));
path.pop_back();
}
}
path.push_back(curr->val);
if (curr->left)
this->Dfs(curr->left, target, sum+curr->val, path);
if (curr->right)
this->Dfs(curr->right, target, sum+curr->val, path);
path.pop_back();
}
};