Code Interview Note
  • 0. Introduction
  • 1. Basic
    • Python Basic
    • Java Basic
    • Primitive Type
    • Basic Question
    • Number
  • 2. Array and Numbers
    • General
    • TwoSum
    • Buy and Sell Stock
    • SubArray
      • SubArray + HashMap
    • Sliding Window
      • Sliding Window At Most Problem
    • Word Break
    • Passes Problem
    • Majority Element
    • Partition Array
    • Sort Colors
    • Anagram
    • Ugly Number
    • TwoPointer
    • Swipe Line
    • Calculator
    • Sudoku
  • 2.1 String
    • String
    • Palindrome
    • Parentheses
    • Decode String
    • Calculator
    • Abbreviation
  • 3. Linkedlist
    • Dummy Node
    • Double Pointers
  • 4. Stack and Queue
    • General
    • Increase/Decrease Stack
  • 5. Binary Search
    • General
    • BS on result
    • Save the half which has result
    • Rotated Sorted Array
    • Split Array Largest Sum
  • 6. Binary Tree
    • General
    • Path Sum
    • Lowest Common Ancestor
    • BST
    • Convert
    • Traverse
    • Valid Ordered Tree
    • Construct Binary Tree
    • Tree depth and width
    • Vertical Order Traverse
  • 7. Heap
    • Geneal
    • TopK
  • 8. Simulation
    • General
    • Read4
    • Encode Decode
    • LRU/LFU
    • Robot
    • GetRandom O(1)
    • Probability
  • 9. DFS
    • Backtrack
    • General
    • Subset
    • Permutation
    • Combination
  • 10. HashTable
    • General
  • 11. Sort
    • General
  • 12. Recursion
    • General
  • 13. Dynamic Programming
    • Graph
    • General
    • Coordinate
    • Double Sequence
    • Longest Common Subsequence
    • Rolling Array
    • House Robber
    • Backpack
    • Memorization
    • Diagonal
  • 14. BFS
    • General
    • Number of Islands
    • The Maze
  • 15. Graph
    • Shortest Path
    • Undirected Graph
    • Topology Sort
    • Word Ladder
    • Tarjan's Algo
  • 16. Divide & Conquer
    • General
  • 17. UnionFind
    • General
    • Grouping
  • 18. Trie
    • General
    • Word Square
  • 19. Company Summary
    • Oracle
    • Amazon
      • DP
    • Google
    • Hackerrank
    • LinkedIn
  • 20. Design
  • 21. Math
  • Behavior Question
  • Internet
  • OS
Powered by GitBook
On this page
  • 112 Path Sum
  • 113 Path Sum II
  • 437. Path Sum III
  • Binary Tree Maximum Path Sum - root to any
  • 124 Binary Tree Maximum Path Sum - any to any

Was this helpful?

  1. 6. Binary Tree

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))
PreviousGeneralNextLowest Common Ancestor

Last updated 4 years ago

Was this helpful?