Leo Lei | 雷雨
Aug 11, 2018
The difference between Path Sum III and Path Sum II is for III the path does not need to start or end at the root or a leaf, which creates a lot of possibilities.
A brute-force way is using the method that solves II to check all the subtrees and return the accumulated count. It would be a nested recursion, which has the O(N2) time complexity.
There is actually an O(N) dynamic programming solution which solve the problem in O(N) time. I am still trying to figure out the details (TODO).
# Brute force
class Solution(object):
cnt = 0
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
# helper function to find the valid paths that extends from root to its children
def preorder(node, curr_sum):
if node:
curr_sum += node.val
if curr_sum == sum:
self.cnt += 1
preorder(node.left, curr_sum)
preorder(node.right, curr_sum)
# check root and left/right child
preorder(root, 0)
if root:
self.pathSum(root.left, sum)
self.pathSum(root.right, sum)
return self.cntJunior: The Stanford Entry in the Urban Challenge
How to build an autonomous car from the scratch :)
Abstract: This article presents the architecture of Junior, a robotic vehicle capable of navigating urban environments autonomously. In doing so, the vehicle is able to select its own routes, perceive and interact with other traffic, and execute various urban driving skills including lane changes, U-turns, parking, and merging into moving traffic. The vehicle successfully finished and won second place in the DARPA Urban Challenge, a robot competition organized by the U.S. Government.
Cubic Spline interpolation in C++
None.