Leetcode 1379. 找出克隆二叉树中的相同节点

Table of Contents

题解
#

方法一：递归解法
#

思路
#

首先，original 节点用不到，其次我们可以使用递归来解决这个问题。对于每个结点，我们首先判断当前结点是否为空，如果是，则返回空指针。然后判断当前结点是否为目标节点，如果是，则返回当前结点的副本。如果当前结点不是目标节点，则递归遍历左子树和右子树，分别在左子树和右子树中查找目标节点。

复杂度分析
#

时间复杂度：对于每个结点，我们遍历它一次，所以时间复杂度为 O(n)，其中 n 是二叉树中的结点数。
空间复杂度：递归调用的栈空间最大为二叉树的高度，最坏情况下为 O(n)，其中 n 是二叉树中的结点数。

实现
#

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:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return find_target_copy(original, cloned, target);
    }

    TreeNode* find_target_copy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (original == nullptr || cloned == nullptr) {
            return nullptr;
        }

        if (cloned->val == target->val) {
            return cloned;
        }

        auto r1 = find_target_copy(original, cloned->left, target);
        if (r1) {
            return r1;
        }
        
        return find_target_copy(original, cloned->right, target);
    }
};