從LeetCode學演算法 - 108 Tree (20) / DFS (17)

1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree (Medium)

寫在前面

好久不見！筆者最近剛換了工作，
所以比較忙一點XD 之後1月中會有HiSKIO 技術年貨節的活動，
歡迎大家拿著折價券來修從LeetCode學演算法的課程喲！
如果預算不夠，相信這108篇也還是很夠讀者練習的啦XDD

在更之後還有規劃0元挑戰賽的部分，
只要修課後一定時間內成功錄取新工作 ，
課程就會全額退費喲！ 這部分再請留意官方那邊的公告，
如果有開始的話，文章中也會再提醒各位。

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/leetcodeadv

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/leetcodeall

Question

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are ** not allowed** to change any of the two trees or the target node and the answer ** must be** a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1

1
2
3
Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2

1
2
Input: tree = [7], target =  7
Output: 7

Example 3

1
2
Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4

1
2
Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5

1
2
Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

分析/解題

給定兩個二元樹 original 跟 cloned ，
並給定一個 originl 樹上的參考節點 target，
當中，cloned是original的完全複製，
請找到 cloned 上和 target 相對應的相同節點回傳。
留意兩棵樹上的節點都不允許被改變，
且答案必須要是cloned這棵樹上的對應節點。
(而不是original上的或新作出來的節點)

條件限制：

樹上的總節點數量範圍在1到10⁴之間。
樹上的各節點值均為獨一無二 的。
target是original這棵樹上的節點，且不為null。

後續：如果重複值可被允許，嘗試在這個條件下解決問題。

這題雖然標為Medium，但說實在的不難XD
看完題目以後，已經經歷過前面各種難題的讀者，
應該會直覺想到使用DFS來解決。

那麼，由於題目一開始已經給定說值是全部獨一無二。
如果先不計較Follow up的部分，
其實我們可以直接比較值就可以了！
我們可以直接將target的值當作目標，
並且對於cloned這棵樹進行dfs，只要比較到相同的值，
就可以進行回傳啦！
由於1的關係，我們不用擔心使用遞迴會超過call stack限制，
使用一個helper函式，當遇到null/None時，
回傳null/None，接著檢查所在節點值是否和target的值相同 ；
接著分別dfs往左邊和往右邊的樹進行尋找 。

當左邊已經找到時，我們可以不用再檢查右邊的部分 ，
直接回傳得到的節點；否則當右邊有找到時，回傳右邊得到的節點 ；
當右邊也沒有找到時，則回傳null/None 。

那麼，如果節點值不一定獨一無二呢？
那麼我們就要同時也將original一起進行遞迴，
這時候檢查的就是original上歷經的節點是否是target節點，
在檢查到的時候同時去回傳cloned的對應節點。

這時候我們用來檢查相等的就是記憶體位址，而非節點值 。
因為唯有記憶體位址相同時，能保證這個節點是對應位置的那個節點。
(而非只有裡面的值相同)

依此，我們寫成程式碼如下：

Java

Java的部分我們額外提供了LeetCode上Follow Up的解法在註解，
使用相同的做法，應該也可以寫出Python的方法，
讀者可以自行嘗試看看。

Python

Python的部分，請讀者留意，
對Python而言，我們寫n: TreeNode, v: int這樣的格式，
是寫給人看的 XD，讀者也可以完全都不寫，一樣可以執行。
而且對於使用者來說，就算你將v代成不是int的東西，
也不會直接被Python視為錯誤，
並不像Java或其他程式語言那樣對這邊有型別檢查，
這點請務必留意喲！

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，基本上最差的狀況要遍歷整棵樹，
而空間上要計較Call Stack的話，則會跟樹的深度成正比，
除此以外沒有其他額外和N相關的部分)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve