Проблема:

Рассмотрим все листья бинарного дерева. В порядке слева направо значения этих листьев формируют последовательность конечных значений.

Например, в приведенном выше дереве последовательность конечных значений равна (6, 7, 4, 9, 8).

Два бинарных дерева считаются похожими на листья, если их последовательность значений листьев одинакова.

Вернуть true тогда и только тогда, когда два заданных дерева с головными узлами root1 и root2 подобны листьям.

Достаточно просто!!! Обратите внимание, что в этом случае мы можем сделать своего рода упрощенную DFS: нам не нужно отслеживать «посещенные» узлы (поскольку это дерево, которое является однонаправленным и ациклическим). Также обратите внимание, что подойдет ТОЛЬКО DFS: BFS даст нам неправильный результат в случае, если листья одинаковы, но принадлежат разным родительским узлам.

И как мы реализуем DFS? Конечно, с помощью STACK!!!

class Solution:
    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def isLeaf(node):
            if not node: return False
            return not (node.left or node.right)
        
        def traverse(root):
            leaves = []
            s = [ root ]
            while s:
                n = s.pop()              
               
                if n.left:
                    s.append(n.left)
                if n.right:
                    s.append(n.right)
                if isLeaf(n):
                    leaves.insert(0, n)
                    
            return leaves
        
        leaves1 = traverse(root1)
        leaves2 = traverse(root2)
 
        if len(leaves1) != len(leaves2): return False
        
        for i,l in enumerate(leaves1):
            if l.val != leaves2[i].val:
                return False
        return True

Более Pythonesque способ сделать это:

def leafSimilar(self, root1, root2):
        def traverse(node):
            if node:
                if not node.left and not node.right:
                    yield node.val
                yield from traverse(node.left)
                yield from traverse(node.right)
return list(traverse(root1)) == list(traverse(root2))