Path¶

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

def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
    stack = [(root, 0)]
    ans = 0
    while stack:
        node, path = stack.pop()
        if node:
            path = (path) ^ (1 << node.val)
            if not node.left and not node.right:
                ans += path & (path - 1) == 0
            stack.append((node.right, path))
            stack.append((node.left, path))
    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

def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
    stack = [(root, 0)]
    total = 0
    while stack:
        node, cur_binary = stack.pop()
        if node:
            cur_binary = cur_binary * 2 + node.val
            if not node.left and not node.right:
                total += cur_binary
            stack.append((node.right, cur_binary))
            stack.append((node.left, cur_binary))
    return total

def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
    q = [(root, 0)]
    total = 0
    while q:
        mini_q = []
        while q:
            node, cur_binary = q.pop(0)
            if node:
                cur_binary = cur_binary * 2 + node.val
                if not node.left and not node.right:
                    total += cur_binary
                mini_q.append((node.left, cur_binary))
                mini_q.append((node.right, cur_binary))
        q = mini_q
    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

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    stack = [(root, 0)]
    total = 0
    while stack:
        node, cur_decimal = stack.pop()
        if node:
            cur_decimal = cur_decimal * 10 + node.val
            if not node.left and not node.right:
                total += cur_decimal
            stack.append((node.right, cur_decimal))
            stack.append((node.left, cur_decimal))
    return total

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    q = [(root, 0)]
    total = 0
    while q:
        mini_q = []
        while q:
            node, cur_decimal = q.pop(0)
            if node:
                cur_decimal = cur_decimal * 10 + node.val
                if not node.left and not node.right:
                    total += cur_decimal
                mini_q.append((node.left, cur_decimal))
                mini_q.append((node.right, cur_decimal))
        q = mini_q
    return total