Path

Path

112. Path Sum (Easy)

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    def recursion(root, required):
        if root:
            if not root.left and not root.right and root.val == required:
                return True
            a = recursion(root.left, required - root.val)
            b = recursion(root.right, required - root.val)
            return a or b

    return recursion(root, targetSum)

257. Binary Tree Paths (Easy)

def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
    def recursion(node):
        nonlocal path, paths
        if node:
            path.append(str(node.val))
            if not node.left and not node.right:
                paths.append("->".join(path))
            recursion(node.left) if node.left else None
            recursion(node.right) if node.right else None
            path.pop()

    path = []
    paths = []
    recursion(root)
    return paths

113. Path Sum II (Medium)

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    def recursion(node):
        nonlocal path, path_sum, paths
        if node:
            path.append(node.val)
            path_sum += node.val
            if not node.left and not node.right and path_sum == targetSum:
                paths.append(deepcopy(path))
            recursion(node.left) if node.left else None
            recursion(node.right) if node.right else None
            path.pop()
            path_sum -= node.val

    path_sum = 0
    path = []
    paths = []
    recursion(root)
    return paths

Math in it: Bitwise, Divmod

1457. Pseudo-Palindromic Paths in a Binary Tree (Medium)

Solution

Refer solution for 266. Palindrome Permutation (Easy).

def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
    def recursion(node, path):
        nonlocal ans
        if node:
            path = (path) ^ (1 << node.val)
            if not node.left and not node.right:
                ans += path & (path - 1) == 0
            recursion(node.left, path) if node.left else None
            recursion(node.right, path) if node.right else None

    ans = 0
    recursion(root, 0)
    return ans

1022. Sum of Root To Leaf Binary Numbers (Easy)

def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
    def recursion(node):
        nonlocal total, cur_binary
        if node:
            cur_binary = 2 * cur_binary + node.val
            if not node.left and not node.right:
                total += cur_binary
            recursion(node.left)
            recursion(node.right)
            cur_binary //= 2

    cur_binary = total = 0
    recursion(root)
    return total

129. Sum Root to Leaf Numbers (Medium)

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    def recursion(node):
        nonlocal total, cur_decimal
        if node:
            cur_decimal = 10 * cur_decimal + node.val
            if not node.left and not node.right:
                total += cur_decimal
            recursion(node.left)
            recursion(node.right)
            cur_decimal //= 10

    cur_decimal = total = 0
    recursion(root)
    return total

Simple Path Tracking

404. Sum of Left Leaves (Easy)

def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
    def recursion(node):
        nonlocal total
        if node:
            if node.left and not node.left.left and not node.left.right:
                total += node.left.val
            recursion(node.left)
            recursion(node.right)

    total = 0
    recursion(root)

1469. Find All The Lonely Nodes (Easy)

def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
    def recursion(root):
        if root:
            if root.left and root.right:
                ...
            elif root.left or root.right:
                lone_node = root.left or root.right
                lone_wolves.append(lone_node.val)
            recursion(root.left)
            recursion(root.right)

    lone_wolves = []
    recursion(root)
    return lone_wolve