題目鏈接

Leetcode.1379 找出克隆二叉樹中的相同節(jié)點 easy

題目描述

給你兩棵二叉樹，原始樹 original和克隆樹 cloned，以及一個位于原始樹 original中的目標節(jié)點 target。

其中，克隆樹 cloned是原始樹 original的一個 副本 。

請找出在樹 cloned中，與 target相同 的節(jié)點，并返回對該節(jié)點的引用（在 C/C++ 等有指針的語言中返回 節(jié)點指針，其他語言返回節(jié)點本身）。

注意：你 不能 對兩棵二叉樹，以及 target 節(jié)點進行更改。只能 返回對克隆樹 cloned中已有的節(jié)點的引用。

示例 1:

輸入: tree = [7,4,3,null,null,6,19], target = 3
輸出: 3
解釋: 上圖畫出了樹 original 和 cloned。target 節(jié)點在樹 original 中，用綠色標記。答案是樹 cloned 中的黃顏色的節(jié)點（其他示例類似）。

示例 2:

輸入: tree = [7], target = 7
輸出: 7

示例 3:

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

提示：

• 樹中節(jié)點的數(shù)量范圍為 $[1,10^4]$ 。
• 同一棵樹中，沒有值相同的節(jié)點。
• target節(jié)點是樹 original中的一個節(jié)點，并且不會是 null。

解法：遞歸

遞歸遍歷 cloned，找到與 target值相同的結(jié)點返回即可。

時間復(fù)雜度： $O(n)$

C++代碼：

class Solution {
public:TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {if(cloned == nullptr) return nullptr;if(cloned->val == target->val) return cloned;auto a = getTargetCopy(original,cloned->left,target);if(a != nullptr) return a;else return getTargetCopy(original,cloned->right,target);}
};

Python代碼：

class Solution:def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:if cloned == None:return Noneif cloned.val == target.val:return cloneda = self.getTargetCopy(original,cloned.left,target)if a != None:return aelse:return self.getTargetCopy(original,cloned.right,target)