Recursion with Return

Recursion with Return

606. Construct String from Binary Tree (Medium)

def tree2str(self, root: Optional[TreeNode]) -> str:
    def recursion(node):
        if node:
            left_subtree = recursion(node.left) or []
            right_subtree = recursion(node.right) or []
            if left_subtree:
                left_subtree = ["("] + left_subtree + [")"]
            if right_subtree:
                right_subtree = ["("] + right_subtree + [")"]
            if not left_subtree and right_subtree:
                left_subtree = ["()"]
            return [str(node.val)] + left_subtree + right_subtree

    ans = recursion(root)
    return "".join(ans)

508. Most Frequent Subtree Sum (Medium)

def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
    def recursion(node):
        nonlocal hm, max_count, most_frequent
        if node:
            left_sum = recursion(node.left)
            right_sum = recursion(node.right)
            total = left_sum + right_sum + node.val
            hm[total] += 1
            if max_count < hm[total]:
                max_count = hm[total]
                most_frequent = [total]
            elif max_count == hm[total]:
                most_frequent.append(total)
            return total
        return 0

    hm = defaultdict(int)
    max_count = most_frequent = 0
    recursion(root)
    return most_frequent

226. Invert Binary Tree (Easy)

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    def recursion(node):
        if node:
            prev_left = node.left
            node.left = recursion(node.right)
            node.right = recursion(prev_left)
            return node

    recursion(root)
    return root

250. Count Univalue Subtrees (Medium)

def recursion(node):
    nonlocal count
    if not node:
        return True
    ans = True
    if node.left and node.right:
        ans = node.val == node.left.val == node.right.val
    elif node.left or node.right:
        child = node.left or node.right
        ans = node.val == child.val
    left = recursion(node.left)
    right = recursion(node.right)
    count += ans and left and right
    return ans


count = 0
recursion(root)
return count

1026. Maximum Difference Between Node and Ancestor (Medium)

def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
    def recursion(node, max_node, min_node):
        if not node:
            return 0
        max_node = max(max_node, node.val)
        min_node = min(min_node, node.val)

        left = recursion(node.left, max_node, min_node)
        right = recursion(node.right, max_node, min_node)
        return max(left, right, abs(max_node - min_node))

    return recursion(root, root.val, root.val)