mirror of
https://github.com/autistic-symposium/master-algorithms-py.git
synced 2025-04-29 12:16:14 -04:00
27 lines
688 B
Python
27 lines
688 B
Python
#!/usr/bin/env python3
|
|
# -*- coding: utf-8 -*-
|
|
# author: bt3gl
|
|
|
|
|
|
def has_path_sum(root, target_sum) -> bool:
|
|
|
|
def transverse(node, sum_here=0):
|
|
|
|
if not node:
|
|
return sum_here == target_sum
|
|
|
|
sum_here += node.val
|
|
|
|
if not node.left:
|
|
return transverse(node.right, sum_here)
|
|
if not node.right:
|
|
return transverse(node.left, sum_here)
|
|
else:
|
|
return transverse(node.left, sum_here) or transverse(node.right, sum_here)
|
|
|
|
if not root:
|
|
return False
|
|
|
|
return transverse(root)
|
|
|