博文中会简要介绍Leetcode P0112题目分析及解题思路。
“Path Sum”是一道比较基础的题目，利用深度优先搜索。由于需要求从根结点到叶子结点的路径上所有值的和，解法上是本层依赖下层结果，所以这里采取递归回溯的方法。
一旦最后叶子结点的值加上前面路径上的所有值的和等于目标值，则返回true，最终每个树结点返回左子树和右子树的逻辑或的结果。
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 boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
return this.traverse(root, sum, 0);
}
private boolean traverse(TreeNode curr, int target, int sum) {
if (curr.left == null && curr.right == null)
return (sum+curr.val == target);
boolean left = false, right = false;
if (curr.left != null)
left = this.traverse(curr.left, target, sum+curr.val);
if (curr.right != null)
right = this.traverse(curr.right, target, sum+curr.val);
return left || right;
}
}
以下是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:
bool hasPathSum(TreeNode* root, int sum) {
if (!root)
return false;
return this->Traverse(root, sum, 0);
}
private:
bool Traverse(TreeNode *curr, int target, int sum) {
if (!curr->left && !curr->right)
return (sum+curr->val == target);
bool left = false, right = false;
if (curr->left)
left = this->Traverse(curr->left, target, sum+curr->val);
if (curr->right)
right = this->Traverse(curr->right, target, sum+curr->val);
return (left || right);
}
};