如何遍历两棵相同的树和return一个目标值？

Question

有人能告诉我为什么 console.log 输出正确答案，而 return 输出空值吗？

我试图遍历两棵相同的树，然后当在原始树中的节点中找到目标值时，我试图return克隆树中的相同节点值。

非常感谢您提供的任何帮助。

原题：https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/

代码库：

var getTargetCopy = function(original, cloned, target) {
    if(original === null) {
        return null
    }
    
    original.left = getTargetCopy(original.left, cloned.left, target)
    original.right = getTargetCopy(original.right, cloned.right, target)
    
    if(original.val === target.val) {
        console.log(cloned.val)
        return cloned.val
    }
};

输入：

Your input:
original = [7,4,3,null,null,6,19]
cloned = [7,4,3,null,null,6,19]
target.val = 3

Console.log:

stdout:
3

输出：

Output:
null

想要的答案：

Expected:
3

Answer 1

一些问题：

该函数应该return一个节点，而不是一个值，所以return cloned.val是错误的。应该是return cloned

使用以下语句，您正在变异原始树：

original.left = getTargetCopy(original.left, cloned.left, target)
original.right = getTargetCopy(original.right, cloned.right, target)

这不应该发生。

with if(original.val === target.val) 当 target.val 不是唯一值时，您的代码可能会出现误报。相反，您应该比较节点 reference.
当你有匹配项时，你不应该进行更深入的递归，所以在进行递归调用之前执行此测试。

当递归调用return一个节点时，应该立即return那个节点，不要做任何其他的递归调用。

这里是你的代码更正：

var getTargetCopy = function(original, cloned, target) { if(original === null) { return null } if(original === target) { return cloned; } return getTargetCopy(original.left, cloned.left, target) || getTargetCopy(original.right, cloned.right, target) };

再浓缩一点，可以是：

var getTargetCopy = (original, cloned, target) => !original || original === target ? cloned : getTargetCopy(original.left, cloned.left, target) || getTargetCopy(original.right, cloned.right, target);

如何遍历两棵相同的树和return一个目标值？

How do I traverse two identical trees and return a target value?

javascript

binary-search-tree