Проблема:
Рассмотрим все листья бинарного дерева. В порядке слева направо значения этих листьев формируют последовательность конечных значений.
Например, в приведенном выше дереве последовательность конечных значений равна
(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))