难度: Easy
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
示例 1：
输入：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] 输出：true
示例 2：
输入：root1 = [1,2,3], root2 = [1,3,2] 输出：false
提示：
[1, 200] 范围内[0, 200] 范围内运行时间: 22 ms
内存: 16.0 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
a = []
b =[]
def dp1(x):
if x.left ==None and x.right == None:
a.append(x.val)
if x.left != None:
dp1(x.left)
if x.right!= None:
dp1(x.right)
def dp2(x):
if x.left ==None and x.right == None:
b.append(x.val)
if x.left != None:
dp2(x.left)
if x.right!= None:
dp2(x.right)
dp1(root1)
dp2(root2)
return True if a==b else False
此题解的主要思路是通过两个辅助函数（dp1和dp2）来分别遍历两棵二叉树，并在遍历过程中收集每棵树的所有叶子节点的值。这些值被存储在两个列表a和b中。在遍历完成后，比较这两个列表。如果两个列表相同，说明两棵树的叶值序列相同，函数返回true；否则返回false。遍历树使用的是深度优先搜索（DFS）。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
a = [] # 存储root1的叶子节点值
b = [] # 存储root2的叶子节点值
def dp1(x):
if x.left == None and x.right == None: # 判断是否为叶子节点
a.append(x.val) # 是叶子节点则添加到列表a
if x.left != None:
dp1(x.left) # 递归访问左子树
if x.right != None:
dp1(x.right) # 递归访问右子树
def dp2(x):
if x.left == None and x.right == None: # 判断是否为叶子节点
b.append(x.val) # 是叶子节点则添加到列表b
if x.left != None:
dp2(x.left) # 递归访问左子树
if x.right != None:
dp2(x.right) # 递归访问右子树
dp1(root1) # 收集root1的叶子节点值
dp2(root2) # 收集root2的叶子节点值
return a == b # 比较两个列表，如果相同则返回true，否则返回false
深度优先搜索（DFS）通常被选择来收集叶子节点的值，因为它可以有效地遍历到每一个叶子节点而无需遍历树中所有的层级。在DFS中，我们可以从根节点直接深入到叶子节点，而不需要首先遍历所有同层的节点。这使得我们可以在找到叶子节点时立即处理它们，而不必存储额外的节点信息或维持一个复杂的队列结构，这通常是BFS所需要的。此外，DFS的递归实现简洁，直观易于理解和编码，这也是它常被用于此类问题的原因。
在比较两个叶子序列列表时，如果两棵树的叶子节点数目不相等，那么这两个列表将不会相等。在Python中，列表比较首先检查长度，如果长度不同则直接返回False。因此，如果两棵树的叶子节点数量不同，即使它们的部分叶子节点值相同，最终的比较结果也会是False，表示两棵树的叶值序列不相似。
在二叉树的数据结构中，通常一个节点的值为null意味着该节点不存在，因此在实际的树遍历中我们不会遇到值为null的节点。在Python和许多其他编程语言中，不存在的节点通常表示为None，且不会作为叶子节点处理。题解中的dp1和dp2函数在遍历过程中会检查节点是否存在（即是否为None），只有存在的节点才会进一步检查是否为叶子节点。因此，题解已经隐式地处理了值为null（None）的情况，只有非null节点可以成为叶子节点并被添加到列表中。
题解中对于叶子节点的判断是基于节点的左右子节点是否为null，这种方法适用于所有标准的二叉树结构。在标准二叉树中，一个叶子节点定义为没有子节点的节点。因此，当一个节点的左右子节点都为null时，可以确定它是一个叶子节点。这种判断方法是二叉树中识别叶子节点的常规和有效方式。