Path Sum

112 Path Sum

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))