What is the best traversal method to solve the problem 'Find a Corresponding Node of a Binary Tree in a Clone of That Tree'?

Both DFS and BFS are effective for this problem. The choice depends on your preference and the tree structure, but both have a time complexity of O(N).

Can I solve this problem in less than O(N) time?

No, because you need to examine each node at least once in the worst case. Thus, O(N) is the optimal time complexity for this problem.

How do I track the state between the original and cloned trees during traversal?

You can track the state by ensuring that for every node visited in the original tree, the corresponding node is visited in the cloned tree. This can be done by following the same traversal path in both trees.

What are the constraints of the 'Find a Corresponding Node of a Binary Tree in a Clone of That Tree' problem?

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

What should I do if the binary trees are not perfectly balanced?

The solution approach works regardless of whether the trees are balanced or not. Both DFS and BFS will traverse all nodes in the tree without any assumptions about balance.

#1379

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

找出克隆二叉树中的相同节点

给你两棵二叉树，原始树 original 和克隆树 cloned ，以及一个位于原始树 original 中的目标节点 target 。其中，克隆树 cloned 是原始树 original 的一个副本。请找出在树 cloned 中，与 target 相同的节点，并返回对该节点的引用（在 …

树深度优先搜索广度优先搜索二叉树

题目描述

给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。

其中，克隆树 cloned 是原始树 original 的一个副本。

请找出在树 cloned 中，与 target 相同的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回节点指针，其他语言返回节点本身）。

注意：你不能对两棵二叉树，以及 target 节点进行更改。只能返回对克隆树 cloned 中已有的节点的引用。

示例 1:

输入: tree = [7,4,3,null,null,6,19], target = 3
输出: 3
解释: 上图画出了树 original 和 cloned。target 节点在树 original 中，用绿色标记。答案是树 cloned 中的黄颜色的节点（其他示例类似）。

示例 2:

输入: tree = [7], target =  7
输出: 7

示例 3:

输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
输出: 4

提示：

树中节点的数量范围为 [1, 10⁴] 。
同一棵树中，没有值相同的节点。
target 节点是树 original 中的一个节点，并且不会是 null 。

进阶：如果树中允许出现值相同的节点，将如何解答？

lightbulb

解题思路

方法一：DFS

我们设计一个函数 $dfs(root1, root2)$ ，它会在树 $root1$ 和 $root2$ 中同时进行 DFS 遍历，当遍历到某个节点时，如果这个节点恰好为 $target$ ，那么我们就返回 $root2$ 中对应的节点。否则，我们递归地在 $root1$ 和 $root2$ 的左右子树中寻找 $target$ ，并返回找到的结果中不为空的那一个。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是树中节点的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def getTargetCopy(
        self, original: TreeNode, cloned: TreeNode, target: TreeNode
    ) -> TreeNode:
        def dfs(root1: TreeNode, root2: TreeNode) -> TreeNode:
            if root1 is None:
                return None
            if root1 == target:
                return root2
            return dfs(root1.left, root2.left) or dfs(root1.right, root2.right)

        return dfs(original, cloned)

speed

复杂度分析

指标	值
时间	\mathcal{O}(N)
空间	up to

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's understanding of binary tree traversal techniques.
question_mark
Assesses the ability to maintain state during traversal.
question_mark
Tests problem-solving skills in efficiently matching nodes between original and cloned trees.

warning

常见陷阱

外企场景

error
Confusing the target node in the original tree with its corresponding node in the cloned tree.
error
Using an inefficient traversal that leads to unnecessary computations.
error
Failing to track the state correctly between the two trees during traversal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Different traversal methods: DFS vs BFS for the tree search.
arrow_right_alt
Handling trees of varying sizes and depths.
arrow_right_alt
Finding corresponding nodes in a non-binary tree (extension to n-ary trees).

help

常见问题

外企场景

继续练习

#1361 验证二叉树 #1315 祖父节点值为偶数的节点和 #1448 统计二叉树中好节点的数目