1. 題目
給你兩棵二叉樹，原始樹 original 和克隆樹 cloned，以及一個位于原始樹 original 中的目標節點 target。
其中，克隆樹 cloned 是原始樹 original 的一個 副本 。
請找出在樹 cloned 中，與 target 相同 的節點，并返回對該節點的引用（在 C/C++ 等有指針的語言中返回 節點指針，其他語言返回節點本身）。
注意：
你 不能 對兩棵二叉樹，以及 target 節點進行更改。
只能 返回對克隆樹 cloned 中已有的節點的引用。
進階：如果樹中允許出現值相同的節點，你將如何解答？
1
2
3
4
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
循環方式的二叉樹遍歷，兩棵樹同步進行即可
class Solution {
public:
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
stack<TreeNode*> stk1, stk2;
TreeNode *tp1, *tp2;
while(original || !stk1.empty())
{
while(original)
{
stk1.push(original);
original = original->left;
}
while(cloned)
{
stk2.push(cloned);
cloned = cloned->left;
}
tp1 = stk1.top();
tp2 = stk2.top();
stk1.pop();
stk2.pop();
if(tp1 == target)
return tp2;
original = tp1->right;
cloned = tp2->right;
}
return NULL;
}
};
872 ms 164.6 MB
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
