宝宝也能看懂的 leetcode 周赛 - 169 - 2

1305. All Elements in Two Binary Search Trees

Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 题解。

这里是第 169 期的第 2 题,也是题目列表中的第 1305 题 -- 『All Elements in Two Binary Search Trees』

题目描述

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

example 1

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

example 5

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

  • Each tree has at most 5000 nodes.
  • Each node's value is between [-10^5, 10^5].

官方难度

MEDIUM

解决思路

题目内容很短,有两个二叉搜索树,需要把它们里面的所有值放进一个数组中,并且结果是要保持顺序递增的。

读完之后第一反应,这题还真是直白呀,没包装个什么描述性的说法,搞的我都不好写文章了,哼 >.<

关于什么是二叉搜索树,这个大家可以自行搜索,当然我之后也会写文章介绍常见的数据结构,一不小心给自己开了个新坑。

对于这道题目的要求,我们可以遍历这两个二叉搜索树,得到所有的值放进新数组中,然后再进行排序。当然,既然是非常科班的题目,自然有很套路的应对方式。毕竟一涉及到基于比较的排序,那复杂度就直接上 O(nlogn) 了。

直接方案

我们想要得到符合递增顺序的二叉搜索树内的所有值,直接进行中序遍历即可,需要的时间复杂度是 O(n)。关于什么是中序遍历,同样我会在新坑里面提到。这里先不做过多展开。

然后对于两个有序数组进行合并,我们可以这样做:

  1. 取得两个数组中各自的最小值,即第一个值
  2. 把它们进行比较,得到的小值一定是当前所有剩余的未合并元素中的最小值
  3. 把这个小值从数组开头剔除掉,放进最终的结果的末端
  4. 重复回到步骤 1,直到有一个数组空了
  5. 把剩下的那个数组中的值直接添加进结果的末端

这样我们只需要 O(n) 的时间复杂度即可完成合并了。

当然在实际代码中,我们还可以做一些优化,例如并不把数组开头的值剔除掉,而是使用一个索引标识当前访问的位置。因为对于数组这样的线性表,我们剃掉第一值也就意味着后续所有值的前移,代价还是很大的。

const getAllElements = (root1, root2) => {
  const arr1 = [];
  const arr2 = [];
  traversal(root1, arr1);
  traversal(root2, arr2);
  const ret = [];
  let idx1 = idx2 = 0;
  while (idx1 < arr1.length && idx2 < arr2.length) {
    arr1[idx1] < arr2[idx2] ? ret.push(arr1[idx1++]) : ret.push(arr2[idx2++]);
  }
  while (idx1 < arr1.length) ret.push(arr1[idx1++]);
  while (idx2 < arr2.length) ret.push(arr2[idx2++]);
  return ret;

  function traversal(node, arr) {
    if (!node) return;
    traversal(node.left, arr);
    arr.push(node.val);
    traversal(node.right, arr);
  }
};

上面的代码跑到了 208ms,暂时 beats 100%。不过我跑完之后回头一看,不得不说,写的真丑。要是 code review 看到这样的代码,我肯定是不会合并的。那我们把它改的稍微好看一点吧。

const traversal = (node, arr = []) => {
  if (node) {
    traversal(node.left, arr);
    arr.push(node.val);
    traversal(node.right, arr);
  }
  return arr;
};
const merge = (arr1, arr2) => {
  const ret = [];
  let idx1 = idx2 = 0;
  while (idx1 < arr1.length && idx2 < arr2.length) {
    arr1[idx1] < arr2[idx2] ? ret.push(arr1[idx1++]) : ret.push(arr2[idx2++]);
  }
  while (idx1 < arr1.length) ret.push(arr1[idx1++]);
  while (idx2 < arr2.length) ret.push(arr2[idx2++]);
  return ret;
};
const getAllElements = (root1, root2) => merge(traversal(root1), traversal(root2));

总结

这是一道比较套路的题,需要一点点科班知识,即二叉搜索树和中序遍历。相信大家应该很容易就能掌握这种套路了吧。

那么最后加一个小思考,上面代码中的 merge 方法是否可以改为支持不定数量的数组合并呢,即 const merge = (...list) => {}。希望小伙伴们能帮帮张小猪,么么嗒 >.<

相关链接

Image placeholder
zhangleilei
未设置
  95人点赞

没有讨论,发表一下自己的看法吧

推荐文章
宝宝也能看懂的 leetcode 周赛 - 169 - 1

1304.FindNUniqueIntegersSumuptoZeroHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第1题,也是题目列表中的第1304题

宝宝也能看懂的 leetcode 周赛 - 169 - 3

1306.JumpGameIIIHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第3题,也是题目列表中的第1306题--『JumpGameIII』题目描述

宝宝也能看懂的 leetcode 周赛 - 169 - 4

1307.VerbalArithmeticPuzzleHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第4题,也是题目列表中的第1307题--『Verba

我从来不觉得程序员是吃青春饭的!这里有169万份分析数据

阅读本文约需要5分钟程序员这个职业究竟可以干多少年,在中国这片神奇的土地上,很多人都说只能干到30岁,然后就需要转型。在很多面试中,问到应聘者未来的规划都能听到好些应聘都说程序员是个青春饭。因为,大多

pymysql fetchone () , fetchall () , fetchmany ()

最近在用python操作mysql数据库时,碰到了下面这两个函数,标记一下: 1.定义 1.1fetchone(): 返回单个的元组,也就是一条记录(row),如果没有结果则返回None 1.2fet

LeetCode 刷题笔记

从AmazonOA高频题开始 总结每一道做过的题目,先总结一下思路,然后记录从中获取的新知识。题目顺序不是按照序号顺序的,而是题目在真实面试中出现的频率排序。由于之前已经做过一些了,所以那些题目暂时还

用 Rust 刷 leetcode 第二题

Problem Youaregiventwonon-emptylinkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredinre

用 Rust 刷 leetcode 第一题

problemGivenanarrayofintegers,return indices ofthetwonumberssuchthattheyadduptoaspecifictarget. Youm

用 Rust 刷 leetcode 第二题

ProblemYouaregiventwo non-empty linkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredin 

LeetCode 112. 路径总和

描述给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明:叶子节点是指没有子节点的节点。注意点:必须联通到叶节点分析从根节点开始,每当遇到一个

算法-最小栈-LeetCode155

题目最小栈设计一个支持push,pop,top操作,并能在常数时间内检索到最小元素的栈。push(x) --将元素x推入栈中。pop() --删除栈顶的元素。top() --获取栈顶元素。getMin

算法-下一个更大元素 I-LeetCode.496

题目下一个更大的元素I给定两个没有重复元素的数组 nums1和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数

Leetcode上最南的是哪道题?

大家伙想要找份好工作,刷题是一道绕不过的坎,Leetcode大家都很熟悉了,很多公司面试的时候会用上面的原题,今天我们就来看看这Leetcode上的题!首先依然通过利索的爬虫获取了Leetcode官网

php 解题leetcode 97 交错字符串

课程推荐:PHP开发工程师--学习猿地精品课程 题目描述:给定三个字符串s1,s2,s3,验证s3是否是由s1和s2交错组成的。 测试样例:输入: s1="accccaabbccabccabbcaab

php 解题leetcode 282 移动零

课程推荐:PHP开发工程师--学习猿地精品课程 题目描述leetcode282问题,数组问题 给定一个数组nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入:[

全网最通俗易懂的Kafka入门

前言只有光头才能变强。文本已收录至我的GitHub仓库,欢迎Star:https://github.com/ZhongFuCheng3y/3y众所周知,消息队列的产品有好几种,这里我选择学习Kafka

终于有篇看的懂的 B 树文章了!

索引,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述完整。本文就来从头到尾介绍下数据库的索引。索引是一种数据结构,用于

前端都该懂的浏览器工作原理,你懂了吗?

课程推荐《前端开发工程师--学习猿地精品课程》 前言在我们面试过程中,面试官经常会问到这么一个问题,那就是从在浏览器地址栏中输入URL到页面显示,浏览器到底发生了什么?这个问题看起来是老生常谈,但是这

程序员必懂的Redis技术实战

课程推荐:前端开发工程师--学习猿地精品课程 Redis是现在很受欢迎的NoSQL数据库之一,目前广泛用于缓存系统、分布式锁、计数器、消息队列系统、排行榜、社交网络等场景中,本篇文章成哥为大家带来re

一篇文章看懂,存储虚拟化在不同用例中的实践与优势

存储虚拟化是一种对物理存储资源进行抽象的技术,使其看起来像是一个集中的资源。虚拟化掩盖了管理内存、网络、服务器和存储中资源的复杂性。存储虚拟化运行在多个存储设备上,使它们看起来就像一个单一的存储池。这

一文看懂web服务器、应用服务器、web容器、反向代理服务器区别与联系

课程推荐《web全栈开发就业班--拿到offer再缴学费--融职教育》 1.1.Web服务器概念与基本原理 1.1.1.Web服务器的历史1989年,互联网之父Berners-Lee向其雇主CERN提

Python爬虫:手把手教你采集登陆后才能看到数据

课程推荐:Python开发工程师--学习猿地--送9个上线商业项目 爬虫在采集网站的过程中,部分数据价值较高的网站,会限制访客的访问行为。这种时候建议通过登录的方式,获取目标网站的cookie,然后再

DeepFakes进化版DeepNude惊现!一键“脱衣“,火到宕机

大数据文摘出品作者:蒋宝尚、赵伟人工智能的黑暗面能有多黑?这边DeepFake带来的余震还没有被平息,本周,又一AI偏门应用爆出,一键直接“脱掉”女性的衣服!海外媒体Motherboard测试图片显然

IEEE态度转变:解除对华为评审限制

大数据文摘出品作者:周素云、魏子敏IEEE的态度发生变化。今晨,IEEE电气电子工程师学会中国官网及官方公众号同时发出声明,表示IEEE向美国商务部要求就出口管制条例在IEEE出版活动的适用性做出说明

PHP跌出前十,铁打的 Python 连续3年第一:IEEE Spectrum 2019编程语言排行榜出炉

Python势头不减,依旧第一,而且进一步拉开了与其他语言的差距。这一结果,来自IEEESpectrum2019年度编程语言排行榜。这已经是Python连续3年保持第一。在Python之下,第二交椅的