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

【LetMeFly】1379.找出克隆二叉树中的相同节点:二叉树遍历

力扣题目链接:https://leetcode.cn/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/

给你两棵二叉树,原始树 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, 104] 。
  • 同一棵树中,没有值相同的节点。
  • target 节点是树 original 中的一个节点,并且不会是 null 。

 

进阶:如果树中允许出现值相同的节点,将如何解答?

解题方法:二叉树遍历

这道题根被不需要管original树,只需要按照任意的方式遍历cloned树,并在遍历的过程中判断当前节点是否和target节点相同即可。

这里以(伪)广度优先搜索为例:

创建一个队列,队列中初始元素为cloned树的根节点。

之后开始不断地从队列中取出节点:

  • 如果当前节点和target的值相等,则直接返回该节点,算法结束。
  • 如果当前节点的左子节点非空,则将左子节点加入队列中。
  • 如果当前节点的右子节点非空,则将右子节点加入队列中。
  • 时间复杂度$O(N)$,其中$N$为二叉树节点个数。
  • 空间复杂度$O(N)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
queue<TreeNode*> q;
q.push(cloned);
while (true) { // 一定会找到
TreeNode* thisNode = q.front();
q.pop();
if (thisNode->val == target->val) {
return thisNode;
}
if (thisNode->left) {
q.push(thisNode->left);
}
if (thisNode->right) {
q.push(thisNode->right);
}
}
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# # 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:
q = [cloned]
while True:
thisNode = q.pop()
if thisNode.val == target.val:
return thisNode
if thisNode.left:
q.append(thisNode.left)
if thisNode.right:
q.append(thisNode.right)

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/137341930


1379.找出克隆二叉树中的相同节点
https://blog.letmefly.xyz/2024/04/03/LeetCode 1379.找出克隆二叉树中的相同节点/
作者
Tisfy
发布于
2024年4月3日
许可协议