力扣1379题：找出克隆二叉树中的目标节点 - 递归解法详解

内容简介

本文详细解析了力扣第1379题"找出克隆二叉树中的目标节点"的递归解法。通过深度优先搜索遍历克隆树，找到与原始树目标节点值相同的节点。这种方法时间复杂度为O(n)，是理解二叉树遍历和节点查找的经典解法。文章包含完整注释代码、算法思路讲解和复杂度分析。

算法思路

1.递归遍历‌：使用深度优先搜索(DFS)遍历克隆二叉树

2‌.节点匹配‌：比较当前节点值与目标节点值

3‌.终止条件‌：找到匹配节点或遍历完整棵树

4.‌左右子树搜索‌：分别在左右子树中递归查找目标节点

代码实现（带详细注释）

class Solution {
public:
    // 递归函数：在克隆树中查找与目标节点对应的节点
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (cloned == nullptr)  // 克隆树当前节点为空，返回nullptr
            return nullptr;
        
        // 当前节点值与目标节点值匹配，返回当前节点
        if (target->val == cloned->val) 
            return cloned;
        
        // 先在左子树中查找
        if (getTargetCopy(original, cloned->left, target))
            return getTargetCopy(original, cloned->left, target);
        else  // 左子树未找到则在右子树中查找
            return getTargetCopy(original, cloned->right, target);
    }
};

复杂度分析

‌时间复杂度‌：O(n)，最坏情况下需要遍历整棵树

‌空间复杂度‌：O(h)，递归栈空间，h为树的高度

优化方向

‌迭代实现‌：使用栈代替递归，减少函数调用开销

‌提前终止‌：找到目标节点后立即返回，避免不必要的搜索

‌并行搜索‌：对于大型树结构，可以考虑并行搜索左右子树

总结

本文提供的递归解法是查找克隆二叉树中目标节点的高效解决方案，通过DFS遍历和值比较，实现了简洁明了的算法实现。理解这种解法有助于掌握二叉树遍历和节点查找的基本技巧。