872. 叶子相似的树

# 872\. 叶子相似的树

[https://leetcode-cn.com/problems/leaf-similar-trees/](https://leetcode-cn.com/problems/leaf-similar-trees/)

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

![](/media/202105/2021-05-11_232141.png)

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

# 解答

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 深度优先搜索
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function(root1, root2) {
    const leaf1 = [];
    // 获取所有叶子节点的值
    dfs(root1, leaf1);
    const leaf2 = [];
    dfs(root2, leaf2);
    // 转成字符串判断是否相同
    return leaf1.toString() === leaf2.toString();
};

/**
 * 获取所有叶子节点 
 */
function dfs(root, res){
    if(!root) return root;
    if(!root.left && !root.right) {
        res.push(root.val);
    }
    dfs(root.left, res);
    dfs(root.right, res);
}
```