"""
LC 863 - All Nodes Distance K in Binary Tree

Problem: Find all nodes at distance k from a target node.

Example:
    Input:  [3,5,1,6,2,0,8,null,null,7,4], target=5, k=2
    Output: [7,4,1]

Constraints:
    - Number of nodes: [1, 500], all unique values
    - 0 <= k <= 1000
"""
from typing import List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while q and i < len(vals):
        node = q.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i]); q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i]); q.append(node.right)
        i += 1
    return root


class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # Approach: build parent map so we can traverse upward,
        # then BFS from target in all 3 directions (left, right, parent) — O(n)
        parent = {}

        def build_parents(node, par=None):
            if not node: return
            parent[node] = par
            build_parents(node.left, node)
            build_parents(node.right, node)

        build_parents(root)

        # BFS from target, avoid revisiting
        queue = deque([(target, 0)])
        visited = {target}
        result = []
        while queue:
            node, dist = queue.popleft()
            if dist == k:
                result.append(node.val)
                continue
            for neighbor in (node.left, node.right, parent[node]):
                if neighbor and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))
        return result


if __name__ == "__main__":
    sol = Solution()
    root = build_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])

    def find(node, val):
        if not node: return None
        if node.val == val: return node
        return find(node.left, val) or find(node.right, val)

    assert sorted(sol.distanceK(root, find(root, 5), 2)) == sorted([7, 4, 1])
    assert sol.distanceK(root, find(root, 5), 0) == [5]
    print("All tests passed.")

"""
# LC 110: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced — every node's left and
right subtrees differ in height by at most 1.

## Examples
```text
Input:  root = [3, 9, 20, null, null, 15, 7]
Output: true

Input:  root = [1, 2, 2, 3, 3, null, null, 4, 4]
Output: false

Input:  root = []
Output: true
```

## Constraints
- The number of nodes in the tree is in the range [0, 5000].
- -10^4 <= Node.val <= 10^4
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Solution:
    """
    ## 110. Balanced Binary Tree

    Given a binary tree, determine if it is height-balanced.

    A height-balanced binary tree is a binary tree in which the depth of the two subtrees
    of every node never differs by more than one.

    ### Examples

    ```text
    Input:  root = [3, 9, 20, null, null, 15, 7]
    Output: true

    Input:  root = [1, 2, 2, 3, 3, null, null, 4, 4]
    Output: false

    Input:  root = []
    Output: true
    ```

    ### Constraints

    - The number of nodes in the tree is in the range `[0, 5000]`.
    - `-10^4 <= Node.val <= 10^4`
    """

    def isBalanced_topdown(self, root: Optional[TreeNode]) -> bool:
        # Time: O(n^2), Space: O(n)
        def height(node):
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        if not root:
            return True
        if abs(height(root.left) - height(root.right)) > 1:
            return False
        return self.isBalanced_topdown(root.left) and self.isBalanced_topdown(root.right)

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # Return height if balanced, -1 if not; propagate -1 upward on imbalance
        # A node is balanced if both subtrees are balanced and heights differ by <= 1
        # Time: O(n), Space: O(n)
        def check(node):
            if not node:
                return 0
            left = check(node.left)
            if left == -1:
                return -1
            right = check(node.right)
            if right == -1:
                return -1
            if abs(left - right) > 1:
                return -1
            return 1 + max(left, right)

        return check(root) != -1


if __name__ == '__main__':
    s = Solution()

    assert s.isBalanced(build_tree([3, 9, 20, None, None, 15, 7])) is True
    assert s.isBalanced_topdown(build_tree([3, 9, 20, None, None, 15, 7])) is True

    assert s.isBalanced(build_tree([1, 2, 2, 3, 3, None, None, 4, 4])) is False
    assert s.isBalanced(None) is True

    print("All tests passed.")

"""
# LC 94: Binary Tree Inorder Traversal

Return the inorder traversal (left -> root -> right) of a binary tree's node values.

## Examples
```text
Input:  root = [1, null, 2, 3]
Output: [1, 3, 2]

Input:  root = []
Output: []

Input:  root = [1]
Output: [1]
```

## Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Solution:
    """
    ## 94. Binary Tree Inorder Traversal

    Given the `root` of a binary tree, return the inorder traversal of its nodes' values.

    ### Examples

    ```text
    Input:  root = [1, null, 2, 3]
    Output: [1, 3, 2]

    Input:  root = []
    Output: []

    Input:  root = [1]
    Output: [1]
    ```

    ### Constraints

    - The number of nodes in the tree is in the range `[0, 100]`.
    - `-100 <= Node.val <= 100`
    """

    def inorderTraversal_recursive(self, root: Optional[TreeNode]) -> List[int]:
        # Time: O(n), Space: O(n)
        result = []
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        dfs(root)
        return result

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # Recursive in-order: left subtree, root, right subtree
        # Time: O(n), Space: O(n)
        result, stack = [], []
        curr = root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            result.append(curr.val)
            curr = curr.right
        return result


if __name__ == '__main__':
    s = Solution()

    root = build_tree([1, None, 2, 3])
    assert s.inorderTraversal(root) == [1, 3, 2]
    assert s.inorderTraversal_recursive(build_tree([1, None, 2, 3])) == [1, 3, 2]

    assert s.inorderTraversal(None) == []
    assert s.inorderTraversal(build_tree([1])) == [1]

    print("All tests passed.")

"""
# LC 102: Binary Tree Level Order Traversal

Return the level-order traversal of a binary tree as a list of lists (one list per
level, left to right).

## Examples
```text
Input:  root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]

Input:  root = [1]
Output: [[1]]

Input:  root = []
Output: []
```

## Constraints
- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Solution:
    """
    ## 102. Binary Tree Level Order Traversal

    Given the `root` of a binary tree, return the level order traversal of its nodes' values
    (i.e., from left to right, level by level).

    ### Examples

    ```text
    Example 1:
    Input:  root = [3,9,20,null,null,15,7]
    Output: [[3],[9,20],[15,7]]

    Example 2:
    Input:  root = [1]
    Output: [[1]]

    Example 3:
    Input:  root = []
    Output: []
    ```

    ### Constraints
    - The number of nodes in the tree is in the range `[0, 2000]`.
    - `-1000 <= Node.val <= 1000`
    """

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # BFS with a queue; process all nodes at current level before moving to next
        # Time: O(n), Space: O(n) — process nodes level by level using a queue
        if not root:
            return []
        result, queue = [], deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

    def levelOrder_dfs(self, root: Optional[TreeNode]) -> List[List[int]]:
        # DFS with depth index; extend result list when reaching a new depth level
        # Time: O(n), Space: O(n) — use recursion depth as level index
        result = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return
            if depth == len(result):
                result.append([])
            result[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return result


if __name__ == '__main__':
    sol = Solution()

    root = build_tree([3, 9, 20, None, None, 15, 7])
    assert sol.levelOrder(root) == [[3], [9, 20], [15, 7]]
    assert sol.levelOrder_dfs(root) == [[3], [9, 20], [15, 7]]

    assert sol.levelOrder(build_tree([1])) == [[1]]
    assert sol.levelOrder(None) == []

    print("All tests passed.")

"""
# LC 124: Binary Tree Maximum Path Sum

Find the maximum sum of any path in a binary tree. A path is any sequence of nodes
connected by edges; it does not need to pass through the root.

## Examples
```text
Input:  root = [1, 2, 3]
Output: 6

Input:  root = [-10, 9, 20, null, null, 15, 7]
Output: 42
```

## Constraints
- The number of nodes in the tree is in the range [1, 3 * 10^4].
- -1000 <= Node.val <= 1000
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Solution:
    """
    ## 124. Binary Tree Maximum Path Sum

    A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in
    the sequence has an edge connecting them. A node can only appear in the sequence **at most
    once**. Note that the path does not need to pass through the root.

    The **path sum** of a path is the sum of the node's values in the path.

    Given the `root` of a binary tree, return the maximum path sum of any **non-empty** path.

    ---

    ### Examples

    ```text
    Example 1:
        Input:  root = [1, 2, 3]
        Output: 6
        Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

    Example 2:
        Input:  root = [-10, 9, 20, null, null, 15, 7]
        Output: 42
        Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
    ```

    ---

    ### Constraints

    - The number of nodes in the tree is in the range [1, 3 * 10^4].
    - -1000 <= Node.val <= 1000
    """

    def maxPathSum(self, root: Optional[TreeNode]) -> int:  # O(n) time, O(h) space
        # For each node, max path through it = node.val + max(0, left) + max(0, right)
        # Update global max; return node.val + max(0, best single branch) to parent
        self.max_sum = float('-inf')

        def dfs(node):
            if not node:
                return 0
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)
            self.max_sum = max(self.max_sum, node.val + left + right)
            return node.val + max(left, right)

        dfs(root)
        return self.max_sum


if __name__ == '__main__':
    s = Solution()

    root1 = build_tree([1, 2, 3])
    assert s.maxPathSum(root1) == 6

    root2 = build_tree([-10, 9, 20, None, None, 15, 7])
    assert s.maxPathSum(root2) == 42

    root3 = build_tree([-3])
    assert s.maxPathSum(root3) == -3

    print("All tests passed.")

"""
# LC 145: Binary Tree Postorder Traversal

Return the postorder traversal (left -> right -> root) of a binary tree's node values.

## Examples
```text
Input:  root = [1, null, 2, 3]
Output: [3, 2, 1]

Input:  root = []
Output: []

Input:  root = [1]
Output: [1]
```

## Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Solution:
    """
    ## 145. Binary Tree Postorder Traversal

    Given the `root` of a binary tree, return the postorder traversal of its nodes' values.

    ### Examples

    ```text
    Input:  root = [1, null, 2, 3]
    Output: [3, 2, 1]

    Input:  root = []
    Output: []

    Input:  root = [1]
    Output: [1]
    ```

    ### Constraints

    - The number of nodes in the tree is in the range `[0, 100]`.
    - `-100 <= Node.val <= 100`
    """

    def postorderTraversal_recursive(self, root: Optional[TreeNode]) -> List[int]:
        # Time: O(n), Space: O(n)
        result = []
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            result.append(node.val)
        dfs(root)
        return result

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # Recursive post-order: left subtree, right subtree, root
        # Time: O(n), Space: O(n)
        if not root:
            return []
        stack1, stack2 = [root], []
        while stack1:
            node = stack1.pop()
            stack2.append(node.val)
            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)
        return stack2[::-1]


if __name__ == '__main__':
    s = Solution()

    assert s.postorderTraversal(build_tree([1, None, 2, 3])) == [3, 2, 1]
    assert s.postorderTraversal_recursive(build_tree([1, None, 2, 3])) == [3, 2, 1]

    assert s.postorderTraversal(None) == []
    assert s.postorderTraversal(build_tree([1])) == [1]

    print("All tests passed.")

"""
# LC 144: Binary Tree Preorder Traversal

Return the preorder traversal (root -> left -> right) of a binary tree's node values.

## Examples
```text
Input:  root = [1, null, 2, 3]
Output: [1, 2, 3]

Input:  root = []
Output: []

Input:  root = [1]
Output: [1]
```

## Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Solution:
    """
    ## 144. Binary Tree Preorder Traversal

    Given the `root` of a binary tree, return the preorder traversal of its nodes' values.

    ### Examples

    ```text
    Input:  root = [1, null, 2, 3]
    Output: [1, 2, 3]

    Input:  root = []
    Output: []

    Input:  root = [1]
    Output: [1]
    ```

    ### Constraints

    - The number of nodes in the tree is in the range `[0, 100]`.
    - `-100 <= Node.val <= 100`
    """

    def preorderTraversal_recursive(self, root: Optional[TreeNode]) -> List[int]:
        # Time: O(n), Space: O(n)
        result = []
        def dfs(node):
            if not node:
                return
            result.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return result

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # Recursive pre-order: root, left subtree, right subtree
        # Time: O(n), Space: O(n)
        if not root:
            return []
        result, stack = [], [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result


if __name__ == '__main__':
    s = Solution()

    assert s.preorderTraversal(build_tree([1, None, 2, 3])) == [1, 2, 3]
    assert s.preorderTraversal_recursive(build_tree([1, None, 2, 3])) == [1, 2, 3]

    assert s.preorderTraversal(None) == []
    assert s.preorderTraversal(build_tree([1])) == [1]

    print("All tests passed.")

"""
# LC 199: Binary Tree Right Side View

Return the values of nodes visible when looking at the tree from the right side,
ordered top to bottom.

## Examples
```text
Input:  root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]

Input:  root = [1, null, 3]
Output: [1, 3]

Input:  root = []
Output: []
```

## Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Solution:
    """
    ## 199. Binary Tree Right Side View

    Given the `root` of a binary tree, imagine yourself standing on the right side of it.
    Return the values of the nodes you can see ordered from top to bottom.

    ### Examples

    ```text
    Example 1:
    Input:  root = [1,2,3,null,5,null,4]
    Output: [1,3,4]

    Example 2:
    Input:  root = [1,null,3]
    Output: [1,3]

    Example 3:
    Input:  root = []
    Output: []
    ```

    ### Constraints
    - The number of nodes in the tree is in the range `[0, 100]`.
    - `-100 <= Node.val <= 100`
    """

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # BFS level by level; the last node in each level is visible from the right
        # Time: O(n), Space: O(n) — take the last node of each BFS level
        if not root:
            return []
        result, queue = [], deque([root])
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.popleft()
                if i == level_size - 1:
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

    def rightSideView_dfs(self, root: Optional[TreeNode]) -> List[int]:
        # Time: O(n), Space: O(h) — visit right child first; first visit at each depth is visible
        result = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return
            if depth == len(result):
                result.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result


if __name__ == '__main__':
    sol = Solution()

    root = build_tree([1, 2, 3, None, 5, None, 4])
    assert sol.rightSideView(root) == [1, 3, 4]
    assert sol.rightSideView_dfs(root) == [1, 3, 4]

    root2 = build_tree([1, None, 3])
    assert sol.rightSideView(root2) == [1, 3]
    assert sol.rightSideView_dfs(root2) == [1, 3]

    assert sol.rightSideView(None) == []

    print("All tests passed.")

"""
GFG - Bottom View of Binary Tree

Problem: Return the bottom view of a binary tree — the last node visible at each
horizontal distance when viewed from below.

Example:
    Input:  [1,2,3,4,5,6,7]
    Output: [4,2,6,3,7]

Constraints:
    - Number of nodes: [1, 10^5]
    - 1 <= Node.val <= 10^5
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while q and i < len(vals):
        node = q.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root


class Solution:
    def bottomView(self, root: Optional[TreeNode]) -> List[int]:
        # Approach: BFS with column tracking; keep LAST seen per column — O(n)
        if not root:
            return []

        col_map = {}  # col -> last node val seen (bottom-most)
        queue = deque([(root, 0)])  # (node, col)
        while queue:
            node, col = queue.popleft()
            col_map[col] = node.val  # always overwrite = last seen = bottom view
            if node.left:  queue.append((node.left,  col - 1))
            if node.right: queue.append((node.right, col + 1))

        return [col_map[c] for c in sorted(col_map)]


if __name__ == "__main__":
    sol = Solution()

    root = build_tree([1, 2, 3, 4, 5, 6, 7])
    assert sol.bottomView(root) == [4, 2, 6, 3, 7]

    root2 = build_tree([1, 2, 3])
    assert sol.bottomView(root2) == [2, 1, 3]

    print("All tests passed.")

"""
LC 545 / GFG - Boundary Traversal of Binary Tree

Problem: Return the boundary of a binary tree anticlockwise starting from root.
Boundary = left boundary (excl. leaves) + all leaves + right boundary reversed (excl. leaves).

Example:
    Input:  [1,2,3,4,5,6,7]
    Output: [1,2,4,5,6,7,3]

Constraints:
    - Number of nodes: [1, 10^4]
    - -1000 <= Node.val <= 1000
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while q and i < len(vals):
        node = q.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root


class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        # Approach: three passes — left boundary, leaves, right boundary — O(n)
        if not root:
            return []

        def is_leaf(node):
            return not node.left and not node.right

        def left_boundary(node):
            res = []
            while node:
                if not is_leaf(node):
                    res.append(node.val)
                # prefer left child, fall back to right
                node = node.left if node.left else node.right
            return res

        def leaves(node):
            if not node: return []
            if is_leaf(node): return [node.val]
            return leaves(node.left) + leaves(node.right)

        def right_boundary(node):
            res = []
            while node:
                if not is_leaf(node):
                    res.append(node.val)
                # prefer right child, fall back to left
                node = node.right if node.right else node.left
            return res[::-1]  # reverse so it goes bottom-up

        return (
            [root.val]
            + left_boundary(root.left)
            + leaves(root.left)
            + leaves(root.right)
            + right_boundary(root.right)
        )


if __name__ == "__main__":
    sol = Solution()

    root = build_tree([1, 2, 3, 4, 5, 6, 7])
    assert sol.boundaryOfBinaryTree(root) == [1, 2, 4, 5, 6, 7, 3]

    root2 = build_tree([1])
    assert sol.boundaryOfBinaryTree(root2) == [1]

    print("All tests passed.")

"""
LC 2385 - Amount of Time for Binary Tree to Be Infected

Problem: Starting from node `start`, fire spreads to adjacent nodes each second.
Return the minimum time to burn the entire tree.

Example:
    Input:  [1,5,3,null,4,10,6,9,2], start=3
    Output: 4

Constraints:
    - Number of nodes: [1, 10^5], all unique
    - 1 <= start <= 10^5
"""
from typing import Optional
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while q and i < len(vals):
        node = q.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i]); q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i]); q.append(node.right)
        i += 1
    return root


class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        # Approach: build parent map + locate start node,
        # then BFS spreading in all directions — O(n)
        parent = {}
        start_node = None

        def build(node, par=None):
            nonlocal start_node
            if not node: return
            parent[node] = par
            if node.val == start: start_node = node
            build(node.left, node)
            build(node.right, node)

        build(root)

        visited = {start_node}
        queue = deque([start_node])
        time = -1
        while queue:
            time += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                for nb in (node.left, node.right, parent[node]):
                    if nb and nb not in visited:
                        visited.add(nb)
                        queue.append(nb)
        return time


if __name__ == "__main__":
    sol = Solution()
    assert sol.amountOfTime(build_tree([1, 5, 3, None, 4, 10, 6, 9, 2]), 3) == 4
    assert sol.amountOfTime(build_tree([1]), 1) == 0
    print("All tests passed.")

"""
# LC 105: Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal arrays of a binary tree (all values unique),
reconstruct and return the tree.

## Examples
```text
Input:  preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]

Input:  preorder = [-1], inorder = [-1]
Output: [-1]
```

## Constraints
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- preorder and inorder consist of unique values.
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree_from_list(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


def tree_to_list(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result


class Solution:
    """
    ## 105. Construct Binary Tree from Preorder and Inorder Traversal

    Given two integer arrays `preorder` and `inorder` where:
    - `preorder` is the preorder traversal of a binary tree, and
    - `inorder` is the inorder traversal of the same tree,

    construct and return the binary tree.

    ---

    ### Examples

    ```text
    Example 1:
        Input:  preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
        Output: [3, 9, 20, null, null, 15, 7]

    Example 2:
        Input:  preorder = [-1], inorder = [-1]
        Output: [-1]
    ```

    ---

    ### Constraints

    - 1 <= preorder.length <= 3000
    - inorder.length == preorder.length
    - -3000 <= preorder[i], inorder[i] <= 3000
    - `preorder` and `inorder` consist of unique values.
    - Each value of `inorder` also appears in `preorder`.
    - `preorder` is guaranteed to be the preorder traversal of the tree.
    - `inorder` is guaranteed to be the inorder traversal of the tree.
    """

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:  # O(n^2) time, O(n) space
        # Preorder[0] is always the root; find it in inorder to split left/right
        # Left subtree has len(left_inorder) nodes in preorder; recurse on both halves
        if not preorder:
            return None
        root_val = preorder[0]
        mid = inorder.index(root_val)
        root = TreeNode(root_val)
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return root

    def buildTree_hashmap(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:  # O(n) time, O(n) space
        idx_map = {val: i for i, val in enumerate(inorder)}
        self.pre_idx = 0

        def helper(left, right):
            if left > right:
                return None
            root_val = preorder[self.pre_idx]
            self.pre_idx += 1
            root = TreeNode(root_val)
            mid = idx_map[root_val]
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(inorder) - 1)


if __name__ == '__main__':
    s = Solution()

    pre, ino = [3, 9, 20, 15, 7], [9, 3, 15, 20, 7]
    assert tree_to_list(s.buildTree(pre, ino)) == [3, 9, 20, None, None, 15, 7]
    assert tree_to_list(s.buildTree_hashmap(pre, ino)) == [3, 9, 20, None, None, 15, 7]

    pre2, ino2 = [-1], [-1]
    assert tree_to_list(s.buildTree(pre2, ino2)) == [-1]
    assert tree_to_list(s.buildTree_hashmap(pre2, ino2)) == [-1]

    print("All tests passed.")

"""
# LC 1008: Construct BST from Preorder Traversal

Given an array of integers `preorder` representing the preorder traversal of a BST,
construct and return the BST.

## Examples
```text
Input:  preorder = [8, 5, 1, 7, 10, 12]
Output: [8, 5, 10, 1, 7, null, 12]
```

## Constraints
- 1 <= preorder.length <= 100
- 1 <= preorder[i] <= 1000
- All the values of preorder are unique.
"""
from __future__ import annotations
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(values: list) -> Optional[TreeNode]:
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root


def tree_to_inorder(root: Optional[TreeNode]) -> list:
    result = []
    def dfs(node):
        if node:
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
    dfs(root)
    return result


class Solution:
    # --- Approach 1: Recursive with upper bound O(n) ---
    def bstFromPreorder_recursive(self, preorder: List[int]) -> Optional[TreeNode]:
        self.idx = 0

        def build(upper: float) -> Optional[TreeNode]:
            # If all elements consumed or current value exceeds upper bound, stop
            if self.idx == len(preorder) or preorder[self.idx] > upper:
                return None
            val = preorder[self.idx]
            self.idx += 1
            node = TreeNode(val)
            node.left = build(val)        # left subtree: values < val
            node.right = build(upper)     # right subtree: values < upper
            return node

        return build(float('inf'))

    # --- Approach 2: Stack-based O(n) ---
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        stack = [root]

        for val in preorder[1:]:
            node = TreeNode(val)
            if val < stack[-1].val:
                stack[-1].left = node      # smaller than top → left child
            else:
                # pop until we find the parent (last node smaller than val)
                parent = stack[-1]
                while stack and stack[-1].val < val:
                    parent = stack.pop()
                parent.right = node        # attach as right child
            stack.append(node)

        return root


# ---------- Tests ----------
if __name__ == "__main__":
    sol = Solution()

    # Test 1: standard case
    preorder = [8, 5, 1, 7, 10, 12]
    expected_inorder = sorted(preorder)

    t1 = sol.bstFromPreorder(preorder)
    assert tree_to_inorder(t1) == expected_inorder, f"Got {tree_to_inorder(t1)}"

    t2 = sol.bstFromPreorder_recursive(preorder)
    assert tree_to_inorder(t2) == expected_inorder

    # Test 2: single element
    t = sol.bstFromPreorder([1])
    assert t.val == 1 and t.left is None and t.right is None

    # Test 3: sorted ascending (right-skewed)
    preorder = [1, 2, 3, 4]
    t = sol.bstFromPreorder(preorder)
    assert tree_to_inorder(t) == [1, 2, 3, 4]

    # Test 4: sorted descending (left-skewed)
    preorder = [4, 3, 2, 1]
    t = sol.bstFromPreorder(preorder)
    assert tree_to_inorder(t) == [1, 2, 3, 4]

    print("All tests passed!")

"""
LC 106 - Construct Binary Tree from Inorder and Postorder Traversal

Problem: Build a binary tree given its inorder and postorder traversals.

Example:
    Input:  inorder=[9,3,15,20,7], postorder=[9,15,7,20,3]
    Output: [3,9,20,null,null,15,7]

Constraints:
    - 1 <= len(inorder) <= 3000, all values unique
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while q and i < len(vals):
        node = q.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i]); q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i]); q.append(node.right)
        i += 1
    return root


class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # Approach: last element of postorder is root; find it in inorder to
        # split left/right subtrees. Hash map gives O(1) lookup — O(n) total.
        idx_map = {val: i for i, val in enumerate(inorder)}

        def helper(in_left, in_right):
            if in_left > in_right: return None
            root_val = postorder.pop()          # rightmost = current root
            root = TreeNode(root_val)
            mid = idx_map[root_val]
            # build right before left (postorder pops from end)
            root.right = helper(mid + 1, in_right)
            root.left  = helper(in_left, mid - 1)
            return root

        return helper(0, len(inorder) - 1)


if __name__ == "__main__":
    from collections import deque

    def tree_to_list(root):
        if not root: return []
        res, q = [], deque([root])
        while q:
            node = q.popleft()
            res.append(node.val if node else None)
            if node:
                q.append(node.left)
                q.append(node.right)
        while res and res[-1] is None: res.pop()
        return res

    sol = Solution()
    root = sol.buildTree([9, 3, 15, 20, 7], [9, 15, 7, 20, 3])
    assert tree_to_list(root) == [3, 9, 20, None, None, 15, 7]
    print("All tests passed.")

"""
# LC 427: Construct Quad Tree

Given an n x n binary grid (n is a power of 2), construct a Quad-Tree. Each node is a
leaf if its region is uniform (all 0s or all 1s); otherwise split into four equal
quadrants and recurse.

## Examples
```text
Input:  grid = [[0, 1], [1, 0]]
Output: [[0, 1], [1, 0], [1, 1], [1, 1], [1, 0]]

Input:  grid = [[1, 1], [1, 1]]
Output: [[1, 1]]
```

## Constraints
- n == grid.length == grid[i].length
- n == 2^x where 0 <= x <= 6
- grid[i][j] is 0 or 1.
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight


class Solution:
    """
    ## 427. Construct Quad Tree

    Given a `n * n` matrix `grid` of `0`s and `1`s, return the corresponding Quad-Tree.

    A Quad-Tree is a tree data structure in which each internal node has exactly four children.
    Each node has two attributes:
    - `val`: `True` if the node represents a grid of all `1`s, or `False` if all `0`s. For
      non-leaf nodes, the value can be either `True` or `False`.
    - `isLeaf`: `True` if the node is a leaf node, or `False` if it has four children.

    We can construct a Quad-Tree from a 2D area using the following steps:
    1. If the current grid has the same value (all `1`s or all `0`s), set `isLeaf` to `True`
       and set `val` to the value of the grid and set the four children to `None`.
    2. If the current grid has different values, set `isLeaf` to `False` and set `val` to any
       value and divide the current grid into four sub-grids.
    3. Recurse for each of the children with the proper sub-grid.

    ### Examples

    ```text
    Example 1:
    Input:  grid = [[0,1],[1,0]]
    Output: [[False,False],[True,1],[True,1],[True,1],[True,0]]
    (Serialized quad-tree format)

    Example 2:
    Input:  grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],
                    [1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],
                    [1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
    Output: [[False,False],[True,1],[True,1],[False,False],[True,1],[True,1],[True,0],[True,0],[True,0]]
    ```

    ### Constraints
    - `n == grid.length == grid[i].length`
    - `n == 2^x` where `0 <= x <= 6`
    """

    def construct(self, grid: List[List[int]]) -> 'Node':
        # Check if all values in region are the same — if so, create leaf node
        # Otherwise split into 4 quadrants and recurse on each
        # Time: O(n^2 log n), Space: O(log n) — recursively split grid into four quadrants
        def build(r: int, c: int, size: int) -> Node:
            val = grid[r][c]
            all_same = all(grid[r + dr][c + dc] == val
                           for dr in range(size) for dc in range(size))
            if all_same:
                return Node(bool(val), True)
            half = size // 2
            return Node(
                True, False,
                build(r, c, half),
                build(r, c + half, half),
                build(r + half, c, half),
                build(r + half, c + half, half),
            )

        return build(0, 0, len(grid))


if __name__ == '__main__':
    sol = Solution()

    result = sol.construct([[0, 1], [1, 0]])
    assert result.isLeaf == False
    assert result.topLeft.isLeaf == True and result.topLeft.val == False
    assert result.topRight.isLeaf == True and result.topRight.val == True

    result2 = sol.construct([[1]])
    assert result2.isLeaf == True and result2.val == True

    result3 = sol.construct([[0]])
    assert result3.isLeaf == True and result3.val == False

    print("All tests passed.")

"""
LC 222 - Count Complete Tree Nodes

Problem: Count nodes in a complete binary tree more efficiently than O(n).

Example:
    Input:  [1,2,3,4,5,6]
    Output: 6

Constraints:
    - Number of nodes: [0, 5 * 10^4]
    - Complete binary tree guaranteed
"""
from typing import Optional
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while q and i < len(vals):
        node = q.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i]); q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i]); q.append(node.right)
        i += 1
    return root


class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        # Approach 1: simple DFS — O(n)
        if not root: return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def countNodes_fast(self, root: Optional[TreeNode]) -> int:
        # Approach 2: compare left-most and right-most heights.
        # If equal, left subtree is a perfect binary tree → skip it — O(log^2 n)
        if not root: return 0

        left_h, right_h = 0, 0
        l, r = root, root
        while l: left_h  += 1; l = l.left   # height going left
        while r: right_h += 1; r = r.right  # height going right

        if left_h == right_h:
            return (1 << left_h) - 1  # perfect tree: 2^h - 1 nodes

        # not perfect: recurse on both subtrees
        return 1 + self.countNodes_fast(root.left) + self.countNodes_fast(root.right)


if __name__ == "__main__":
    sol = Solution()
    assert sol.countNodes(build_tree([1, 2, 3, 4, 5, 6])) == 6
    assert sol.countNodes_fast(build_tree([1, 2, 3, 4, 5, 6])) == 6
    assert sol.countNodes_fast(build_tree([])) == 0
    assert sol.countNodes_fast(build_tree([1])) == 1
    print("All tests passed.")

"""
# LC 1448: Count Good Nodes in Binary Tree

A node X is "good" if no node on the path from root to X has a value greater than X.
Return the count of good nodes in the tree.

## Examples
```text
Input:  root = [3, 1, 4, 3, null, 1, 5]
Output: 4

Input:  root = [3, 3, null, 4, 2]
Output: 3

Input:  root = [1]
Output: 1
```

## Constraints
- The number of nodes in the binary tree is in the range [1, 10^5].
- Each node's value is between [-10^4, 10^4].
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


class Solution:
    """
    ## 1448. Count Good Nodes in Binary Tree

    Given a binary tree `root`, a node X in the tree is named **good** if in the path from root
    to X there are no nodes with a value greater than X.

    Return the number of good nodes in the binary tree.

    ### Examples

    ```text
    Example 1:
    Input:  root = [3,1,4,3,null,1,5]
    Output: 4
    Explanation: Nodes 3 (root), 3 (left-left), 4 (right), and 5 (right-right) are good.

    Example 2:
    Input:  root = [3,3,null,4,2]
    Output: 3
    Explanation: Nodes 3 (root), 3 (left), and 4 (left-left) are good.

    Example 3:
    Input:  root = [1]
    Output: 1
    ```

    ### Constraints
    - The number of nodes in the binary tree is in the range `[1, 10^5]`.
    - Each node's value is between `[-10^4, 10^4]`.
    """

    def goodNodes(self, root: TreeNode) -> int:
        # A node is 'good' if its value >= max value seen on path from root
        # DFS passing the running max; count good nodes bottom-up
        # Time: O(n), Space: O(h) — DFS tracking the max value seen on the path from root
        def dfs(node: Optional[TreeNode], max_so_far: int) -> int:
            if not node:
                return 0
            count = 1 if node.val >= max_so_far else 0
            new_max = max(max_so_far, node.val)
            return count + dfs(node.left, new_max) + dfs(node.right, new_max)

        return dfs(root, root.val)


if __name__ == '__main__':
    sol = Solution()

    root = build_tree([3, 1, 4, 3, None, 1, 5])
    assert sol.goodNodes(root) == 4

    root2 = build_tree([3, 3, None, 4, 2])
    assert sol.goodNodes(root2) == 3

    root3 = build_tree([1])
    assert sol.goodNodes(root3) == 1

    print("All tests passed.")

"""
# LC 1325: Delete Leaves With a Given Value

Delete all leaf nodes with value equal to `target`. Repeat until no such leaves remain
(a node that becomes a leaf after deletion should also be deleted if its value equals
`target`).

## Examples
```text
Input:  root = [1, 2, 3, 2, null, 2, 4], target = 2
Output: [1, null, 3, null, 4]

Input:  root = [1, 3, 3, 3, 2], target = 3
Output: [1, 3, null, null, 2]
```

## Constraints
- The number of nodes in the tree is in the range [1, 3000].
- 1 <= Node.val, target <= 1000
"""
from typing import Optional, List
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(vals):
    if not vals:
        return None
    root = TreeNode(vals[0])
    queue = deque([root])
    i = 1
    while queue and i < len(vals):
        node = queue.popleft()
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root


def tree_to_list(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result


class Solution:
    """
    ## 1325. Delete Leaves With a Given Value

    Given a binary tree `root` and an integer `target`, delete all the **leaf nodes** with
    value `target`.

    Note that once you delete a leaf node with value `target`, if its parent node becomes a
    leaf node and has the value `target`, it should also be deleted (you need to continue
    doing this until you can't).

    ---

    ### Examples

    ```text
    Example 1:
        Input:  root = [1, 2, 3, 2, null, 2, 4], target = 2
        Output: [1, null, 3, null, 4]
        Explanation: Leaf nodes with value 2 are removed. Node 2 (left child of root)
                     then becomes a leaf with value 2 and is also removed.

    Example 2:
        Input:  root = [1, 3, 3, 3, 2], target = 3
        Output: [1, 3, null, null, 2]

    Example 3:
        Input:  root = [1, 2, null, 2, null, 2], target = 2
        Output: [1]
    ```

    ---

    ### Constraints

    - The number of nodes in the tree is in the range [1, 3000].
    - 1 <= Node.val, target <= 1000
    """

    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:  # O(n) time, O(h) space
        # Post-order: process children first, then check if current node became a leaf with target value
        if not root:
            return None
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        if not root.left and not root.right and root.val == target:
            return None
        return root


if __name__ == '__main__':
    s = Solution()

    root1 = build_tree([1, 2, 3, 2, None, 2, 4])
    assert tree_to_list(s.removeLeafNodes(root1, 2)) == [1, None, 3, None, 4]

    root2 = build_tree([1, 3, 3, 3, 2])
    assert tree_to_list(s.removeLeafNodes(root2, 3)) == [1, 3, None, None, 2]

    root3 = build_tree([1, 2, None, 2, None, 2])
    assert tree_to_list(s.removeLeafNodes(root3, 2)) == [1]

    print("All tests passed.")