叶子相似的树.md

叶子相似的树

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

示例

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

题解

/**
 * 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/