解决方案


方法:深度优先搜索

思路和算法

首先,让我们找出给定的两个树的叶值序列。之后,我们可以比较它们,看看它们是否相等。

要找出树的叶值序列,我们可以使用深度优先搜索。如果结点是叶子,那么 dfs 函数会写入结点的值,然后递归地探索每个子结点。这可以保证按从左到右的顺序访问每片叶子,因为在右孩子结点之前完全探索了左孩子结点。

复杂度分析

  • 时间复杂度:,其中 是给定的树的长度。

  • 空间复杂度:,存储叶值所使用的空间。