非常感謝你閱讀本文~
歡迎【?點贊】【?收藏】【?評論】~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~

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

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

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

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

注意：

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

進階：如果樹中允許出現(xiàn)值相同的節(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

樣例 4：

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

樣例 5：

輸入: 	tree = [1,2,null,3], target = 2	輸出: 	2

提示：

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

分析

• 這道算法題的需要簡單翻譯一下，三個參數(shù)：第一個參數(shù) original 是原樹；第二個參數(shù) cloned 是第一個參數(shù)的克隆拷貝；第三個參數(shù) target 是我們要找到的節(jié)點，它是第一個參數(shù) original 中的一個節(jié)點，需要找到并返回第二個參數(shù) cloned 里對應(yīng)的節(jié)點。
• 提示中說同一棵樹中，沒有值相同的節(jié)點。所以有的小伙伴可能覺得第一個參數(shù)非常多余，二當家也這么覺得。我們直接遍歷第二個參數(shù) cloned ，直到找到和第三個參數(shù) target 值相同的節(jié)點并返回就可以了。
• 其實第一個參數(shù)在 進階 挑戰(zhàn)里就有用了，如果樹中允許出現(xiàn)值相同的節(jié)點，那就不能用值去判斷是相同節(jié)點了。
• 這時候就需要用到第一個參數(shù) original ，因為第三個參數(shù) target 是原樹中的一個節(jié)點，所以我們可以直接根據(jù)地址判斷是否是相同節(jié)點。
• 第二個參數(shù) cloned 是第一個參數(shù)的克隆拷貝，所以它們具有相同結(jié)構(gòu)，我們只要按照相同順序同時遍歷原樹和克隆樹，就可以找到答案。

題解

java

非遞歸遍歷

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {        Deque<TreeNode> stack      = new LinkedList<>();        TreeNode        node       = original;        TreeNode        clonedNode = cloned;        while (node != null || !stack.isEmpty()) {            if (node != null) {                if (node == target) {                    return clonedNode;                }                stack.push(clonedNode);                stack.push(node);                node = node.left;                clonedNode = clonedNode.left;            } else {                node = stack.pop().right;                clonedNode = stack.pop().right;            }        }        return null;    }}

遞歸遍歷

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {        if (cloned == null                || original == target) {            return cloned;        }        TreeNode ans = getTargetCopy(original.left, cloned.left, target);        if (ans == null) {            ans = getTargetCopy(original.right, cloned.right, target);        }        return ans;    }}

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) {        if (cloned == nullptr            || original == target) {            return cloned;        }        TreeNode* ans = getTargetCopy(original->left, cloned->left, target);        if (ans == nullptr) {            ans = getTargetCopy(original->right, cloned->right, target);        }        return ans;    }};

python

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:        if cloned is None or original == target:            return cloned        ans = self.getTargetCopy(original.left, cloned.left, target)        if ans is None:            ans = self.getTargetCopy(original.right, cloned.right, target)        return ans        

原題傳送門：https://leetcode-cn.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/