叶子相似的树

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

示例

举个例子,如上图所示,给定一颗叶值序列为(6, 7, 4, 9, 8)的树。
如果有两颗二叉树的叶值序列是相同,那么我们就认为它们是叶相似的。 如果给定的两个头结点分别为root1root2的树是叶相似的,则返回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目标数组,之后便结束递归,如果存在左孩子,那么便继续向左递归,如果存在右孩子,那么便继续向右递归,之后便分别对于root1root2的叶子节点置入target1target2数组,之后比较数组长度,若不同则直接返回false,若相同则按每个值进行比较,不同直接返回false,全部相同则在最后返回true

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

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