比较两个二叉树的叶子的递归解决方案返回错误结果

Question

我正在尝试解决LeetCode问题872。叶子相似的树:

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

例如，在上面给定的树中，叶子值序列是

(6, 7, 4, 9, 8)

。

如果两个二叉树的叶子值序列相同，则认为它们是叶子相似。

返回

true

当且仅当给定的两棵具有头节点

root1

和

root2

的树叶子相似。

示例1：

输出：

true

模板代码

/**
 * 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) {
    
};

我的解决方案

var leafSimilar = function(root1, root2) {
    let leaf1 = [];
    let leaf2 = [];
    function dfs(root,leaf){
        if(!root){
            return;
        }
        if(root.left == null && root.right == null){
            leaf.push(root.val);
            return;
        } else {
            dfs(root.left, leaf);
            dfs(root.right,leaf);
        }
        
    }
    dfs(root1, leaf1);
    dfs(root2, leaf2);
    if(leaf1.length !== leaf2.length){return false;}
    leaf1.forEach((element, index) => {
        if(element == leaf2[index]){
            return true;
        }
    });
    return false;
};

它返回的是

false

，而不是上面示例 #1 中预期的

true

。我做错了什么？

Answer 1

问题出在你的

forEach

循环上。在回调中你

return true

，但是那只是退出回调函数，而不是

leafSimilar

。

return

中唯一的

leafSimilar

语句的形式为

return false

，因此它永远不会返回

true

。

要解决此问题，请使用

every

而不是

forEach

。

不是错误，但您可以在该回调中返回布尔表达式

element === leaf2[index]

：

    return leaf1.every((element, index) => element == leaf2[index]);