Boundary of Binary Tree Python Solution

lcpy gen -n 545   # by problem number
lcpy gen -s boundary_of_binary_tree   # by problem name

Input: root = [1,null,2,3,4]
Output: [1,3,4,2]
Explanation:
- The left boundary is empty because the root does not have a left child.
- The right boundary follows the path starting from the root's right child 2 -> 4. 4 is a leaf, so the right boundary is [2].
- The leaves from left to right are [3,4].
Concatenating everything results in [1] + [] + [3,4] + [2] = [1,3,4,2].

Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10]
Output: [1,2,4,7,8,9,10,6,3]
Explanation:
- The left boundary follows the path starting from the root's left child 2 -> 4. 4 is a leaf, so the left boundary is [2].
- The right boundary follows the path down the rightmost path 3 -> 6 -> 10. 10 is a leaf, so the right boundary is [3,6].
- The leaves from left to right are [4,7,8,9,10].
Concatenating everything results in [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3].

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(n)
    def boundary_of_binary_tree(self, root: TreeNode[int] | None) -> list[int]:
        if root is None:
            return []

        def is_leaf(node: TreeNode[int] | None) -> bool:
            return node is not None and node.left is None and node.right is None

        vals = [root.val]

        cur = root.left
        while cur is not None and not is_leaf(cur):
            vals.append(cur.val)
            cur = cur.left if cur.left is not None else cur.right

        leaves: list[int] = []
        stack = [root]
        while stack:
            node = stack.pop()
            if is_leaf(node) and node is not root:
                leaves.append(node.val)
            if node.right is not None:
                stack.append(node.right)
            if node.left is not None:
                stack.append(node.left)
        vals.extend(leaves)

        right: list[int] = []
        cur = root.right
        while cur is not None and not is_leaf(cur):
            right.append(cur.val)
            cur = cur.right if cur.right is not None else cur.left
        vals.extend(reversed(right))
        return vals