[PYTHON] Let Code Day 32 "437. Path Sum III" starting from scratch

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 31 starting from zero "581. Shortest Unsorted Continuous Subarray"

Basically, I would like to solve the easy acceptance in descending order.

Twitter I'm doing it.

By the way, it lasted for a month. Congratulations.

problem

437. Path Sum III The difficulty level is easy. Easy of Top 100 Liked Questions put this in and there are only 3 questions left.

Each node is given a binary tree that contains an integer value.

Sum the node values to find the number of paths that have a particular value sum.

The route does not have to start or end at the parent or leaf, but it must move downwards (only from the parent node to the child node).

Note that the number of nodes in the tree is 1,000 or less, and the range of values is -1,000,000 to 1,000,000.

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1. 5 -> 3

2. 5 -> 2 -> 1
3. -3 -> 11

solution

I solved it with dfs using recursion.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    ans = 0
    def pathSum(self, root: TreeNode, sum: int) -> int:
        def dfs(root,sums,start):
            if not root:
                return 0
            sums -= root.val
            if sums == 0:
                self.ans += 1
            dfs(root.left,sums,False)
            dfs(root.right,sums,False)
            if start:
                dfs(root.left,sum,True)
                dfs(root.right,sum,True)
        dfs(root,sum,True)
        return self.ans
# Runtime: 940 ms, faster than 24.67% of Python3 online submissions for Path Sum III.
# Memory Usage: 15.1 MB, less than 6.82% of Python3 online submissions for Path Sum III.

At first, I thought that I could just call with root and sums, but I couldn't write with that alone (I might be able to write it, but I couldn't think of it now), so when I looked into discuss Almost the same answer, where boolean is used to treat the current node as the starting point. I am using it, and since I was able to implement it very neatly, I will post it as it is.

Even so, people with strong algorithms are amazing ...

You have to work harder.

If there is a good answer, I will add it.