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

## 示例
举个例子，如上图所示，给定一颗叶值序列为`(6, 7, 4, 9, 8)`的树。  
如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是叶相似的。
如果给定的两个头结点分别为`root1`和`root2`的树是叶相似的，则返回`true`；否则返回`false` 。

## 题解

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function(root1, root2) {
    var dfs = function(root, target) {
        if(!root) return ;
        if(!root.left && !root.right) {
            target.push(root.val);
            return ;
        }
        if(root.left) dfs(root.left, target);
        if(root.right) dfs(root.right, target);
    }
    var target1 = [];
    var target2 = [];
    dfs(root1, target1);
    dfs(root2, target2);
    var n1 = target1.length;
    var n2 = target2.length;
    if(n1 !== n2) return false;
    for(let i=0;i<n1;++i){
        if(target1[i] !== target2[i]) return false;
    }
    return true;
};
```

## 思路
对于两棵二叉树，首先定义二叉树深度递归遍历，从左至右获取所有叶子节点，之后进行比较判断所有的叶子是否相同，从而判断这两棵树是否是叶相似的。首先定义深度递归遍历函数`dfs`，如果当前节点为`null`，那么就不在向下递归，如果不存在左节点有叶节点，那么就认为当前节点是叶节点，然后将其推入`target`目标数组，之后便结束递归，如果存在左孩子，那么便继续向左递归，如果存在右孩子，那么便继续向右递归，之后便分别对于`root1`与`root2`的叶子节点置入`target1`与`target2`数组，之后比较数组长度，若不同则直接返回`false`，若相同则按每个值进行比较，不同直接返回`false`，全部相同则在最后返回`true`。

## 每日一题

```
https://github.com/WindrunnerMax/EveryDay
```

## 参考

```
https://leetcode-cn.com/problems/leaf-similar-trees/
```