LeetCode 1379：克隆二叉树对应节点查找的代码问题排查

题目说明 #

给定两棵二叉树original和cloned（cloned是original的完全副本），以及original树中一个节点target的引用。要求返回cloned树中与target对应的节点引用，且不得修改任意树或target节点。

你的代码 #

class Solution {
public: 

    TreeNode* ans = NULL ; 

    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if(cloned == NULL){return cloned ;}
        
        if(cloned->val == target->val){
             ans = cloned ;
        } 
        getTargetCopy(original,cloned->left ,target) ; 
        getTargetCopy(original,cloned->right,target) ;  
        return ans ; 
    }
};

测试用例 #

• 输入：

  [7,4,3,null,null,6,19]
  3
  

• 实际输出：null
• 期望输出：3

问题分析 #

1. 核心逻辑错误：依赖节点值匹配而非结构同步匹配 #

题目中target是original树的节点引用，不是值。你的代码通过cloned->val == target->val匹配节点，这会导致两个问题：

• 如果original树存在多个值与target->val相同的节点，代码会返回第一个遍历到的节点，而非target对应的克隆节点。
• 本次测试用例返回null，本质是这种写法不符合题目设计意图：你没有同步遍历original和cloned，仅遍历cloned树时，可能因遍历顺序或测试框架的内部处理，导致值匹配的条件未被正确触发。

2. 递归效率与结果传递问题 #

• 使用类成员变量ans存储结果，递归过程中即使找到目标节点，仍会遍历完整棵树，浪费性能。同时，成员变量可能在多测试用例场景下被残留值干扰（LeetCode单测试用例虽不会出现，但这不是规范写法）。
• 最初的注释代码中，return getTargetCopy(original,cloned->left ,target)会导致仅遍历左子树，右子树永远不会被访问，直接返回左子树的遍历结果，这也是之前错误的核心原因。

修正方案 #

正确的做法是同步遍历original和cloned树，利用两棵树结构完全一致的特性，当original的当前节点等于target时，直接返回对应的cloned节点：

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        // 遍历到空节点，返回空
        if (original == nullptr) return nullptr;
        // 找到目标节点，返回克隆树的对应节点
        if (original == target) return cloned;
        // 先递归左子树，找到则直接返回
        TreeNode* leftResult = getTargetCopy(original->left, cloned->left, target);
        if (leftResult != nullptr) return leftResult;
        // 左子树没找到，递归右子树
        return getTargetCopy(original->right, cloned->right, target);
    }
};

这个方案的优势：

• 严格遵循题目要求，通过节点引用匹配，不受值重复影响。
• 递归找到目标节点后立即返回，无需遍历整棵树，效率更高。
• 无需使用成员变量，通过递归返回值传递结果，避免多测试用例干扰。

内容的提问来源于stack exchange，提问作者Anthony George