Leaf-Similar Trees Python Solution with Tests

lcpy gen -n 872   # by problem number
lcpy gen -s leaf_similar_trees   # by problem name

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

from leetcode_py import TreeNode


class Solution:
    # Time: O(n + m)
    # Space: O(n + m)
    def leaf_similar(self, root1: TreeNode[int] | None, root2: TreeNode[int] | None) -> bool:
        def leaves(root: TreeNode[int] | None) -> list[int]:
            values: list[int] = []
            stack: list[TreeNode[int] | None] = [root]
            while stack:
                node = stack.pop()
                if not node:
                    continue
                if not node.left and not node.right:
                    values.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
            return values

        return leaves(root1) == leaves(root2)