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.
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False
sum -= root.val
if not root.left and not root.right and sum == 0:
return True
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
113 Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res = []
def helper(node, s, li):
if not node: return
li.append(node.val)
s -= node.val
if not node.left and not node.right and s == 0:
res.append(li.copy())
helper(node.left, s, li)
helper(node.right, s, li)
li.pop()
helper(root, sum, [])
return res
437. Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
class Solution:
count = 0
record = collections.defaultdict(int)
def pathSum(self, root: TreeNode, sum: int) -> int:
self.record[0] = 1
self.helper(root, 0, sum)
return self.count
def helper(self, node, preSum, s):
if not node:
return 0
preSum += node.val
if preSum-s in self.record:
self.count += self.record[preSum - s]
self.record[preSum] += 1
self.helper(node.left, preSum, s)
self.helper(node.right, preSum, s)
self.record[preSum] -= 1
Binary Tree Maximum Path Sum - root to any
From root to any node
public int maxPathSum2(TreeNode root) {
if (root == null) {
return Integer.MIN_VALUE;
}
int left = maxPathSum2(root.left);
int right = maxPathSum2(root.right);
// if number is nagtive, ignore
return root.val + Math.max(0, Math.max(left, right));
}
124 Binary Tree Maximum Path Sum - any to any
Any node to any node
ResultType: rootPath, maxPath
def maxPathSum(self, root: TreeNode) -> int:
self.max = float('-inf')
self.dfs(root)
return self.max
def dfs(self, node):
if not node: return 0
left = self.dfs(node.left)
right = self.dfs(node.right)
self.max = max(self.max, node.val + left + right)
return max(0, node.val + max(left, right))