題目：

請(qǐng)考慮一棵二叉樹上所有的葉子，這些葉子的值按從左到右的順序排列形成一個(gè) 葉值序列 ,。

舉個(gè)例子，如上圖所示,，給定一棵葉值序列為 (6, 7, 4, 9, 8) 的樹,。

如果有兩棵二叉樹的葉值序列是相同，那么我們就認(rèn)為它們是 葉相似 的,。

如果給定的兩個(gè)頭結(jié)點(diǎn)分別為 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], root2 = [1]
輸出：true
示例 3：

輸入：root1 = [1], root2 = [2]
輸出：false
示例 4：

輸入：root1 = [1,2], root2 = [2,2]
輸出：true
示例 5：

輸入：root1 = [1,2,3], root2 = [1,3,2]
輸出：false

提示：

給定的兩棵樹可能會(huì)有 1 到 200 個(gè)結(jié)點(diǎn),。
給定的兩棵樹上的值介于 0 到 200 之間。

解題思路：

思路和算法

首先,，讓我們找出給定的兩個(gè)樹的葉值序列,。之后，我們可以比較它們,，看看它們是否相等,。

要找出樹的葉值序列，我們可以使用深度優(yōu)先搜索,。如果結(jié)點(diǎn)是葉子,，那么 dfs 函數(shù)會(huì)寫入結(jié)點(diǎn)的值,，然后遞歸地探索每個(gè)子結(jié)點(diǎn)。這可以保證按從左到右的順序訪問每片葉子,，因?yàn)樵谟液⒆咏Y(jié)點(diǎn)之前完全探索了左孩子結(jié)點(diǎn),。

代碼：

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaves1 = new ArrayList();
        List<Integer> leaves2 = new ArrayList();
        dfs(root1, leaves1);
        dfs(root2, leaves2);
        return leaves1.equals(leaves2);
    }

    public void dfs(TreeNode node, List<Integer> leafValues) {
        if (node != null) {
            if (node.left == null && node.right == null)
                leafValues.add(node.val);
            dfs(node.left, leafValues);
            dfs(node.right, leafValues);
        }
    }
}