[LeetCode] 931. Minimum Falling Path Sum

 Problem : https://leetcode.com/problems/minimum-falling-path-sum/

A classic DP problem.

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        dp = matrix[0][:]
        tmp = [0] * COLUMN
        
        for y in range(1, ROW):
            for x in range(COLUMN):
                tmp[x] = dp[x]
                
                if x - 1 >= 0:
                    tmp[x] = min(tmp[x], dp[x-1])
                    
                if x + 1 < COLUMN:
                    tmp[x] = min(tmp[x], dp[x+1])
                
                tmp[x] += matrix[y][x]
            
            dp, tmp = tmp, dp
        
        return min(dp)

[LeetCode] 666. Path Sum IV

 Problem : https://leetcode.com/problems/path-sum-iv/

Reconstruct the tree and them use DFS to get the path sums.

Because index starts from 1, for node coordinate (y, x):

-  left child coordinate on next level =  (y + 1,  2 * x - 1)

- right child coordinate on next level = (y + 1,  2 * x)

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        
        tree = {}
        
        for n in nums:
            y = n // 100
            n = n % 100
            x = n // 10
            n = n % 10
            tree[(y, x)] = n
            
        
        def dfs(y, x, sums):
            if (y, x) in tree:
                sums += tree[(y,x)]
                
                # since index starts from 1
                # left child coordination = (y+1, 2*x - 1)
                # right child coordination = (y+1, 2*x)
                if (y+1, 2*x - 1) not in tree and (y+1, 2*x) not in tree:
                    yield sums
                else:
                    yield from dfs(y+1, 2*x-1, sums)
                    yield from dfs(y+1, 2*x, sums)
        
        
        return sum(dfs(1, 1, 0))    
        

[LeetCode] 437. Path Sum III

 Problem : https://leetcode.com/problems/path-sum-iii/

Traval tree in preorder approach. And use prefix-sum to find number of sub-array node value can form the target sum.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        self.result = 0
        
        
        def dfs(node, preSum, seen):
            if node:
                preSum += node.val
                self.result += seen[preSum - targetSum]
                
                seen[preSum] += 1
                
                dfs(node.left, preSum, seen)
                dfs(node.right, preSum, seen)
                    
                seen[preSum] -= 1
        
        
        seen = defaultdict(int)
        seen[0] = 1
        dfs(root, 0, seen)
        return self.result

[LeetCode] 285. Inorder Successor in BST

 Problem : https://leetcode.com/problems/inorder-successor-in-bst/

The recursive approach:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        self.pre = None
        
        def inorder(node):
            if node:
                tmp = inorder(node.left)
                if tmp: return tmp
                
                if self.pre == p:
                    return node
                
                self.pre = node
                
                tmp = inorder(node.right)
                if tmp: return tmp
        
        return inorder(root)

The iterative approach:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        pre = None
        stack = [root]
        
        while stack:
            node = stack[-1]
            
            while node.left:
                stack.append(node.left)
                left = node.left
                node.left = None
                node = left
            
            node = stack.pop()
            if pre == p: 
                return node
            
            pre = node
            
            if node.right:
                stack.append(node.right)
                node.right = None

However the previous 2 approaches do not leverage BST properties.

We can safely discard the left sub-tree, if root.val <= p.val

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        
        result = None
        
        while root:
            if p.val >= root.val:
                root = root.right
            else:
                result = root
                root = root.left
    
        return result