112. Path Sum.md

112. Path Sum

---

leetcode-cn Daily Challenge on July 7th, 2020.

---

Difficulty : Easy

Related Topic : Tree、DFS

---

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.

---

Solution

• mine
  • Java
    • DFS Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.2 MB, less than 72.88% of Java online submissions

      // O(N)time O(D)space
      // N is node count
      // D is root's depth
      public boolean hasPathSum(TreeNode root, int sum) {
          return dfs(root, 0, sum);
      }
      
      boolean dfs(TreeNode node, int count, int sum){
          if(node == null){
              return false;
          }
          count += node.val;
          if(node.left == null && node.right == null){
              return count == sum;
          }
          return dfs(node.left, count, sum) || dfs(node.right, count, sum);
      }
      

---

• the most votes
  • Recursion Runtime: 0 ms, faster than 100.00%, Memory Usage: 41.4 MB, less than 5.04% of Java online submissions

    // O(N)time O(D)space
    // N is node count
    // D is root's depth
    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);
    }
    

---