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)

def tree2str(self, root: Optional[TreeNode]) -> str:
    stack = [(root, False)]
    ans = []
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                ans.append(")")
            else:
                ans.extend(["(", str(node.val)])
                if not node.left and node.right:
                    ans.append("()")
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
    return "".join(ans[1:-1])

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)

def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
    stack = [(root, False, root.val, root.val)]
    max_diff = 0
    while stack:
        node, visited, max_node, min_node = stack.pop()
        if node:
            if visited:
                max_diff = max(max_diff, abs(max_node - min_node))
            else:
                max_node = max(max_node, node.val)
                min_node = min(min_node, node.val)
                stack.append((node.right, False, max_node, min_node))
                stack.append((node.left, False, max_node, min_node))
                stack.append((node, True, max_node, min_node))
    return max_diff