Easy

题目描述

给定两个二叉树 original 和 cloned，以及原始树中一个节点 target 的引用。

克隆树是原始树的副本。

返回克隆树中相同节点的引用。

注意，不允许更改两个树或目标节点，答案必须是克隆树中节点的引用。

示例 1：

输入：tree = [7,4,3,null,null,6,19], target = 3
输出：3
解释：在所有示例中都显示了原始树和克隆树。目标节点是原始树中的绿色节点。答案是克隆树中的黄色节点。

示例 2：

输入：tree = [7], target = 7
输出：7

示例 3：

输入：tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
输出：4

约束条件：

  • 树中节点数在范围 [1, 10^4] 内
  • 树的节点值是唯一的
  • target 节点是原始树中的一个节点且不为 null

进阶： 如果树中允许重复值，你能解决这个问题吗？

解题思路

这道题本质上是在克隆树中找到与原树目标节点值相等的节点。由于题目保证节点值唯一，我们可以采用以下几种方法：

方法一：深度优先搜索（DFS）

最直观的方法是同时遍历原树和克隆树，当在原树中找到目标节点时，返回克隆树中对应位置的节点。我们可以使用递归的方式实现：

  • 如果当前节点为空，返回 null
  • 如果原树的当前节点就是目标节点，返回克隆树的当前节点
  • 否则递归搜索左右子树

方法二：广度优先搜索（BFS）

使用队列同时遍历两个树，当找到目标节点时返回对应的克隆节点。

方法三：值匹配搜索（推荐）

由于节点值唯一，我们可以只在克隆树中搜索值等于目标节点值的节点，这样更简洁高效。

对于进阶问题（允许重复值），我们需要记录从根到目标节点的路径，然后在克隆树中按相同路径找到对应节点。

代码实现

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (!cloned) return nullptr;
        if (cloned->val == target->val) return cloned;
        
        TreeNode* left = getTargetCopy(original, cloned->left, target);
        if (left) return left;
        
        return getTargetCopy(original, cloned->right, target);
    }
};

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if not cloned:
            return None
        if cloned.val == target.val:
            return cloned
        
        left = self.getTargetCopy(original, cloned.left, target)
        if left:
            return left
        
        return self.getTargetCopy(original, cloned.right, target)

public class Solution {
    public TreeNode GetTargetCopy(TreeNode original, TreeNode cloned, TreeNode target) {
        if (cloned == null) return null;
        if (cloned.val == target.val) return cloned;
        
        TreeNode left = GetTargetCopy(original, cloned.left, target);
        if (left != null) return left;
        
        return GetTargetCopy(original, cloned.right, target);
    }
}

var getTargetCopy = function(original, cloned, target) {
    if (!original) return null;
    
    if (original === target) return cloned;
    
    return getTargetCopy(original.left, cloned.left, target) || 
           getTargetCopy(original.right, cloned.right, target);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是树中节点的数量。最坏情况下需要遍历所有节点
空间复杂度O(h)，其中 h 是树的高度。递归调用栈的深度等于树的高度，最坏情况下为 O(n)