Как итеративно проверять симметрию двоичного дерева, чтобы избежать переполнения стека глубокими деревьями в Python [зак ⇐ Python

[Anonymous]

У меня есть работающее рекурсивное решение для проверки симметричности двоичного дерева. Код работает правильно для моих тестовых примеров, но меня беспокоит потенциальное переполнение стека при глубоких деревьях, поскольку в Python есть ограничение рекурсии по умолчанию.

Код: Выделить всё

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

class Solution:
def isSymmetric(self, root):
if root is None:
return True
return self.compare(root.left, root.right)

def compare(self, nodeA, nodeB):
if nodeA is None and nodeB is None:
return True
if nodeA is None or nodeB is None:
return False
if nodeA.val != nodeB.val:
return False
return (self.compare(nodeA.left, nodeB.right) and
self.compare(nodeA.right, nodeB.left))

Вот примеры тестов, которые работают:

Код: Выделить всё

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.right = TreeNode(3)

sol = Solution()
print(sol.isSymmetric(root))  # Output: True

Проблема в том, что при тестировании с деревом глубиной > 1000 узлов я получаю:

Код: Выделить всё

RecursionError: maximum recursion depth exceeded in comparison

Я понимаю, что временная сложность O(n) является оптимальной, но рекурсивный подход использует пространство O(h) в стеке вызовов, где h — высота дерева.
Как я могу преобразовать это рекурсивное решение в итеративное, используя явный стек или очередь, чтобы избежать ограничения рекурсии Python, сохраняя при этом ту же логику сравнения (зеркальное обход слева направо)?
Я пробовал использовать один стек, но я не уверен, как правильно отслеживать оба поддерева одновременно для зеркального сравнения.

Код: Выделить всё

def isSymmetric(self, root):
if not root:
return True
stack = [(root.left, root.right)]

# Not sure how to proceed from here to compare nodes correctly

Как правильно управлять стеком для сравнения пар узлов в зеркальном порядке?

Подробнее здесь: https://stackoverflow.com/questions/797 ... -with-deep