# 872. Leaf-Similar Trees """ consider all levels of a binary tree, from left to right order, the value of those leaves form a leaf value sequence. two binary trees are considered leaf similar if their leafe value sequence is the same. return 1 if and only if the two given trees with head nodes 'root1' and 'root2' are leaf-similar. """ # Definition for a binary tree node. class TreeNode(object): def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution(object): def leafSimilar(self, root1, root2): """ :type root1: TreeNode :type root2: TreeNode :rtype: bool """ def dfs(root): if root is None: return [] leaves = dfs(root.left) + dfs(root.right) return leaves or [root.val] return dfs(root1) == dfs(root2) if __name__ == "__main__": obj = Solution() print( obj.leafSimilar( 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], ) ) # expect: True print(obj.leafSimilar(root1=[1, 2, 3], root2=[1, 3, 2])) # expect: False