LeetCode 112 Path Sum（路径和）（BT、DP）（*）

翻译

给定一个二叉树root和一个和sum，

决定这个树是否存在一条从根到叶子的路径使得沿路所有节点的和等于给定的sum。

例如：
给定如下二叉树和sum=22，
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回真，因为这里存在一条根叶路径（5->4->11->2），它的和为22。

原文

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.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

分析

如果是一个二叉搜索树，那么可以根据它的特性来做一些减法走一下捷径。

先用最基本的方法来求解试试：

bool hasPathSum(TreeNode* root, int sum) {
    if (!root) return false;
    if (!root->left && !root->right) return root->val == sum;
    return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

然后我在想，如果在某个节点上的和已经超过了sum，那应该就false了吧。然后加了一行：

if (root->val > sum) return false;      

噢不……原来还可以有负数的，错了。算了不指望这个了，继续改着玩……

其实这个和上面的差不多，差别在于上面的判断方法是不断的用给定的sum减掉当前的值，而这个是不断往上累加看能否累计到刚好等于sum，还引入了额外的变量……

bool dfs(TreeNode* root, int pasum, int sum) {
    if (!root) return false;
    if (!root->left && !root->right) return pasum + root->val == sum;
    return dfs(root->left, pasum + root->val, sum) || dfs(root->right, pasum+root->val, sum);
}

bool hasPathSum(TreeNode* root, int sum) {
    return dfs(root, 0, sum);
}

代码

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    bool dfs(TreeNode* root, int pasum, int sum) {
        if (!root) return false;
        if (!root->left && !root->right)   return pasum + root->val == sum;
        return dfs(root->left, pasum + root->val, sum) || dfs(root->right, pasum + root->val, sum);
    }
    bool hasPathSum(TreeNode* root, int sum) {
        return dfs(root, 0, sum);
    }
};