题目描述
请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
image.png
举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
提示：
给定的两颗树可能会有 1 到 100 个结点。
示例
示例 1：
解答方法
方法一：深度优先搜索、递归
思路
首先，让我们找出给定的两个树的叶值序列。比较它们是否相等。
要找出树的叶值序列，我们可以使用深度优先搜索。如果结点是叶子，那么 dfs 函数会写入结点的值，然后递归地探索每个子结点。
class Solution:
def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
def dfs(root,res):
if root:
if root.left is None and root.right is None:
res.append(root.val)
dfs(root.left, res)
dfs(root.right, res)
return res
# if dfs(root1,[]) == dfs(root2,[]):
# return True
# else:
# return False
return dfs(root1,[]) == dfs(root2,[])
时间复杂度
O(T1+T2)
空间复杂度
O(T1+T2)
