1379. 找出克隆二叉树中的相同节点 - Find a Corresponding Node of a Binary Tree in a Clone of That Tree

🎯 问题描述（来源于LeetCode）

描述：
给定两棵二叉树 original 和 cloned，以及 original 中的一个目标节点 target。
已知 cloned 是 original 的一个深拷贝（即结构与节点值完全一致，但节点对象不同）。
请返回 cloned 中与 target 对应的节点。

说明：

original 和 cloned 中的节点个数相同，且结构完全一致。
target 节点一定存在于 original 中。
不允许对二叉树进行修改。

示例：

示例 1：

1 2	输入: original = [7,4,3,null,null,6,19], cloned = [7,4,3,null,null,6,19], target = 3 输出: 值为 3 的节点（在 cloned 中对应的节点）

示例 2：

1 2	输入: original = [7], cloned = [7], target = 7 输出: 值为 7 的节点

💻 解题思路

思路1：同步深度优先搜索（DFS）

算法步骤

递归终止条件：
- 如果 original 为 None，说明到达叶子节点的子节点，直接返回 None（未找到）。
检查当前节点：
- 如果 original 就是 target（注意比较的是节点对象，不是值），说明找到了目标节点，此时返回 cloned（对应的克隆树节点）。
递归搜索子树：
- 先在右子树中查找：self.getTargetCopy(original.right, cloned.right, target)。
- 如果右子树找到（返回值不为 None），则直接返回；否则继续在左子树中查找。
- 用 or 连接两次递归调用，因为 or 运算符会短路，先执行右子树，若返回非 None 则直接返回，否则计算左子树并返回其结果。
返回结果：
- 最终返回找到的节点（若未找到则返回 None，但题目保证一定存在）。

思路1：代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

思路1：📊 性能分析

复杂度验证

时间复杂度： $O(n)$ ，其中 $n$ 为二叉树的节点数。最坏情况下需要遍历所有节点（如目标节点在最深层）。
空间复杂度： $O(h)$ ，其中 $h$ 为树的高度。递归调用栈的深度等于树高，最坏情况（链状树）为 $O(n)$ 。

思考

本题的关键是同步递归：每次递归都同时传入 original 和 cloned 的对应节点，确保在原始树中找到 target 时，克隆树中处于相同位置的节点即为答案。
代码中先搜索右子树再搜索左子树，最终使用 or 连接，写法简洁。也可以显式地用变量接收结果后判断，但 or 的短路特性使得代码更紧凑。
此题也可以使用**广度优先搜索（BFS，队列）**同步层序遍历，但 DFS 更直接。
注意比较 original is target（对象身份比较），而不是 original.val == target.val，因为树中可能存在重复值。