Return to Answer

As kinda pointed out already, your lists of nodes/values of the current level are up to \$O(2^n)\$ large. So your large memory usage of 150 MB is no wonder. It could easily be much more. LeetCode must have only very shallow trees (Yeah just checked, max height is only 22. Sigh). Here's somewhat the other extreme, taking only O(1) extra space.

As kinda pointed out already, your lists of nodes/values of the current level are up to \$O(2^n)\$ large. So your large memory usage of 150 MB is no wonder. It could easily be much more. LeetCode must have only very shallow trees (Yeah just checked, max height is only 22. Sigh). Here's somewhat the other extreme, taking only O(1) extra space. And it can handle any tree height, unlike recursive solutions which would at some point exceed the recursion limit and crash.

As pointed out already, your 150 MB memory usage is no wonder, since your lists of nodes/values of the current level are up to \$O(2^n)\$ large. Here's somewhat the other extreme, taking only O(1) extra space.

As kinda pointed out already, your lists of nodes/values of the current level are up to \$O(2^n)\$ large. So your large memory usage of 150 MB is no wonder. It could easily be much more. LeetCode must have only very shallow trees (Yeah just checked, max height is only 22. Sigh). Here's somewhat the other extreme, taking only O(1) extra space.

Yet another version, using getattr and setattr, inspired by this attempt:

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        left = preorder(root.left, 'left', 'right')
        right = preorder(root.right, 'right', 'left')
        result = all(map(operator.eq, left, right))
        for _ in left: pass
        for _ in right: pass
        return result

def preorder(root, kid1, kid2):
    get, set = getattr, setattr
    while root:
        if not get(root, kid1):
            yield root.val
            yield None
            root = get(root, kid2)
            continue
        prev = get(root, kid1)
        while get(prev, kid2) and get(prev, kid2) is not root:
            prev = get(prev, kid2)
        if not get(prev, kid2):
            yield root.val
            set(prev, kid2, root)
            root = get(root, kid1)
        else:
            yield None
            set(prev, kid2, None)
            root = get(root, kid2)
    yield None