1379. Find a Node of a Binary Tree in a Clone Tree
Question
Given two binary trees
original
andcloned
and given a reference to a nodetarget
in the original tree.The
cloned
tree is a copy of theoriginal
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 thecloned
tree.
Solution
DFS搜索,同步递归original和cloned的子节点。
当在original里找到target的时候返回当前的cloned节点。
注意可以先判断一个分支中的返回值是否为空,如果不为空则直接返回。反之则返回另一个分支。这样操作可以进行一部分剪枝。
Code
1 | /** |
1379. Find a Node of a Binary Tree in a Clone Tree
https://xuanhe95.github.io/2022/05/18/1379-Find-a-Node-of-a-Binary-Tree-in-a-Clone-Tree/