基本資料#
難易度: easy 第一次嘗試：2022-11-17
- 提交紀錄：Accepted ×3
解題思路#
複製的樹結構完全一樣，所以兩棵樹同時用同樣的方式走（Tree 模板一）。原樹走到 target（比的是節點本身，值可能重複）時，複製樹上同一步的節點就是答案。
我的解法#
class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
if not original:
return None
if original is target:
return cloned
return (self.getTargetCopy(original.left, cloned.left, target)
or self.getTargetCopy(original.right, cloned.right, target))
複雜度#
時間 O(n)，空間 O(h)。
要特別避免的錯誤#
- 用
is比較節點本身，不要比值。
面試口說整理#
複製樹的結構一樣，所以我兩棵樹同時遞迴，原樹走到目標節點時回傳複製樹上同一個位置的節點。時間 O(n)。