题目描述

给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标结点 target。

其中，克隆树 cloned 是原始树 original 的一个 副本。

请找出在树 cloned 中，与 target 相同 的结点，并返回对该结点的引用。

注意，你 不能 对两棵二叉树，以及 target 结点进行更改。答案应该是对克隆树 cloned 中已有的结点的引用。

进阶：如果树中允许出现值相同的结点，你将如何解答？

样例

输入：tree = [7,4,3,null,null,6,19], target = 3
输出：3
解释：上图画出了树 original 和 cloned。target 结点在树 original 中，用绿色标记。
答案是树 cloned 中的黄颜色的结点（其他示例类似）。

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

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

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

输入：tree = [1,2,null,3], target = 2
输出：2

限制

• 树中结点的数量范围为 [1, 10^4]。
• 同一棵树中，没有值相同的结点。
• target 结点是树 original 中的一个结点，并且不会是 null。

算法

(递归遍历) $O(n)$

1. 从根结点开始递归遍历，递归参数中带有克隆树的指针。
2. 递归的同时记录答案，如果左子树找到了目标值，则不需要再递归右子树。

时间复杂度

• 每个结点仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 系统栈需要额外 $O(h)$ 的空间，其中 $h$ 为树的最大高度。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    void solve(TreeNode* r1, TreeNode* r2, TreeNode* t, TreeNode* &ans) {
        if (!r1) return;

        if (r1 == t) {
            ans = r2;
            return;
        }

        solve(r1->left, r2->left, t, ans);
        if (!ans) solve(r1->right, r2->right, t, ans);
    }

    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        TreeNode *ans;
        ans = NULL;
        solve(original, cloned, target, ans);
        return ans;
    }
};