2015年7月4日星期六

LeetCode: Path Sum

The key is to understand the definition of leaf node: both kids are null, not just one.

From wiki:
An internal node (also known as an inner node, inode for short, or branch node) is any node of a tree that has child nodes. Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.

Use recursion to check every path of the tree: O(n)

 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
/**
 * 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;
        return getSum(root, 0, sum);
    }
    bool getSum(TreeNode* node, int pathsum, int sum ){
        if(node == NULL) {
            return false;
        }
        pathsum+=node->val;
        if(node->left == NULL && node->right == NULL) {
            if(pathsum == sum) return true;
            return false;
        }
        return (getSum(node->left, pathsum, sum) || getSum(node->right, pathsum, sum));
    }
};

If we keep reducing the sum by the traversed node value, then just one function is enough.


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




发帖者 时间：
标签： ,

没有评论:

发表评论

订阅： 博文评论 (Atom)