<commit_before>---
layout: post
title: LeetCode 112
category: 技术
tags: LeetCode Easy
keywords: LeetCode
description: 2019 每天一道题 #112
---

#### [112. Path Sum](https://leetcode.com/problems/path-sum/)
---
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*.

**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.

---
#### Thoughts
---
Count every path's sum value, and then see whether it contains `targetSum`.

**First try:**
```Java
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        List<Integer> all = new ArrayList<>();
        all = helper(root,all,0);
        
        return all.contains(sum);
    }
    public List<Integer> helper(TreeNode root,List<Integer>tmp,int cur){
        // if it's the leaf node
        if(root!=null && root.left==null && root.right==null)
            tmp.add(cur+root.val);
        else if(root!=null){
            helper(root.left,tmp,cur+root.val);
            helper(root.right,tmp,cur+root.val);
        }
        return tmp;
    }
}
```

**Result 1:**
> Runtime: **1 ms**, faster than **14.52%** of Java online submissions for Path Sum.  
Memory Usage: **38.4 MB**, less than **86.41%** of Java online submissions for Path Sum.

Needs to spend some more time on this to speed up my code.

**Second try:**


**Result 2:**
<commit_msg>Update 2019-03-26-LeetCode-112.md<commit_after>---
layout: post
title: LeetCode 112
category: 技术
tags: LeetCode Easy
keywords: LeetCode
description: 2019 每天一道题 #112
---

#### [112. Path Sum](https://leetcode.com/problems/path-sum/)
---
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*.

**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.

---
#### Thoughts
---
Count every path's sum value, and then see whether it contains `targetSum`.

**First try:**
```Java
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        List<Integer> all = new ArrayList<>();
        all = helper(root,all,0);
        
        return all.contains(sum);
    }
    public List<Integer> helper(TreeNode root,List<Integer>tmp,int cur){
        // if it's the leaf node
        if(root!=null && root.left==null && root.right==null)
            tmp.add(cur+root.val);
        else if(root!=null){
            helper(root.left,tmp,cur+root.val);
            helper(root.right,tmp,cur+root.val);
        }
        return tmp;
    }
}
```

**Result 1:**
> Runtime: **1 ms**, faster than **14.52%** of Java online submissions for Path Sum.  
Memory Usage: **38.4 MB**, less than **86.41%** of Java online submissions for Path Sum.

Needs to spend some more time on this to speed up my code.

Update on 2019-03-30, code below copy from: [my-java-solution-...-beats-100](https://leetcode.com/problems/path-sum/discuss/262601/), giving me a new way to solve this problem, brilliant!

**Second try:**
```Java
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null) return false;
        if(root.left==null && root.right==null && (sum-root.val)==0) return true;
        return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
    }
}
```

**Result 2:**
> Runtime: **0 ms**, faster than **100.00%** of Java online submissions for Path Sum.  
Memory Usage: **37.5 MB**, less than **90.69%** of Java online submissions for Path Sum.
{'fraction_non_alphanumeric': 0.1483936766955635, 'fraction_numerical': 0.03518612952575217, 'mean_word_length': 2.700943396226415, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 20, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6425647', 'n_tokens_mistral': 1375, 'n_tokens_neox': 1270, 'n_words': 440}