FXTi's blog
0%

path-sum

Posted on Edited on

Path Sum – LeetCode 112

Problem

Description

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.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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 hasPathSum(TreeNode *root, int sum) {
        if (root == NULL)
            return false;
        else if (root->left == root->right && root->val == sum)
            return true;
        else {
            return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum - root->val);
        }
    }
};

思路

通过在sum上减去当前值来传递状态，寻找val相等的叶节点，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$9$ ms，排名$82.14\%$

Better

思路

BFS的同思路解，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$9$ ms，排名$82.14\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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 hasPathSum(TreeNode *root, int sum) {
        queue<TreeNode *> que;
        que.push(root);
        queue<int> num;
        num.push(sum);
        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i != size; ++i){
                TreeNode *curr = que.front(); que.pop();
                int n = num.front(); num.pop();
                if(!curr) continue;
                if(curr->left == curr->right && curr->val == n)
                    return true;
                que.push(curr->left);
                num.push(n - curr->val);
                que.push(curr->right);
                num.push(n - curr->val);
            }
        }
        return false;
    }
};