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

news/2024/4/17 6:57:04

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

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

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

解题思路

因为这道题目中二叉树的值都是唯一的,所以我们可以直接判断值是否相等来获取到相同的节点。

  • 递归遍历二叉树
  • 判断节点值是否和木匾节点值相等
  • 将找到的节点返回

如果已经找到目标节点或者传入的节点不存在,则直接返回。如果当前节点的值与target的值相等,那么将该节点存储在外部变量res中,表示找到了目标节点。
如果当前节点的值不是目标值,那么递归地在当前节点的左子树和右子树中查找目标节点。

函数开始时初始化res为null,表示还没有找到目标节点。然后调用getNode函数,从cloned树的根节点开始递归搜索。最后,返回res,它将是找到的目标节点,或者在没有找到目标节点的情况下仍然是null。

AC代码

/*** Definition for a binary tree node.* function TreeNode(val) {*     this.val = val;*     this.left = this.right = null;* }*/
/*** @param {TreeNode} original* @param {TreeNode} cloned* @param {TreeNode} target* @return {TreeNode}*/var getTargetCopy = function (original, cloned, target) {let res = null;const getNode = (node) => {if (res || !node) return;if (node.val === target.val) res = node;getNode(node.left);getNode(node.right);};getNode(cloned);return res;
};

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。


https://www.xjx100.cn/news/3366002.html

相关文章

ubuntu16.04不能在主机和虚拟机之间拷贝文本

问题 ubuntu16.04不能在主机和虚拟机之间拷贝文本。 原因 vmware tools没安装好。 解决办法 让虚拟机加载C:\Program Files (x86)\VMware\VMware Workstation\linux.iso光盘文件,设置如下: 拷贝虚拟机光盘中的VMwareTools-10.3.22-15902021.tar.gz文…

SSH中私钥和公钥的使用

在 SSH(Secure Shell)中,密钥对用于加密和身份验证,保证了远程会话的安全。一个密钥对包括两部分:公钥和私钥。它们有不同的作用和特性: 私钥 私钥是一个用户保密的密钥,它绝不能被泄露或分享…

C# 系统学习(框架学习)

WPF实例讲解&#xff1a;创建一个简单的计数器应用 Step 1&#xff1a;创建WPF项目 打开Visual Studio&#xff0c;新建一个WPF应用程序项目。在MainWindow.xaml中添加一个按钮和一个标签控件&#xff0c;用XAML表示如下&#xff1a; <Window x:Class"SimpleCounter…

【Qt】使用Qt实现Web服务器(九):EventSource+JSON实现工业界面数据刷新

1、效果 效果如下,实时刷新温度、湿度 2、源码 2.1 index.html <html><body> <!-- 页面布局,本人对HTML标签不熟悉,凑合看吧 --> <div><label for

Hive安装配置

1 在conf目录下vim 创建hive-site.xml <?xml version"1.0"?> <?xml-stylesheet type"text/xsl" href"configuration.xsl"?> <configuration><property><name>javax.jdo.option.ConnectionURL</name>&l…

Qt5.15以上版本在线安装步骤,可选择更多早期版本

以ubuntu系统为例&#xff1a; 1、先去下载在线安装程序&#xff1a; https://download.qt.io/official_releases/online_installers/ 选择合适的版本&#xff0c;这里是在x64机器的ubuntu虚拟机里安装QT&#xff0c;所以选择如下版本&#xff1a; 或者直接在终端执行如下命令…

FPGA的串口的收发程序设计

module uart_tx(input clk,input rst,input start,input [7:0] data,output reg tx_done,output reg tx_out );// 定义状态机的状态typedef enum logic [2:0] {IDLE, START, DATA, STOP} state_t;reg [10:0] count; // 用于计数发送的位数reg [2:0] state; // 用于记录…

C++初学者:像C#一样写代码,示例程序 RViewer

今天用自己写的窗口类&#xff0c;做了一个程序&#xff0c;用于控制远程电脑 &#xff0c;方便自己的工作。 学习编程的目的&#xff0c;就是为了写程序&#xff0c;做出自己软件。于是&#xff0c;我首先要做的事情是编写一个软件&#xff0c;实现了以下几个功能&#xff1a…