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

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);
    }
};