摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10949人学习

全部文章（共105篇）

题解 | #树的直径# 来自专栏

思路：题目的主要信息：要求树的直径，即树上两点最远距离这里的树不止是二叉树，都有可能题目给的Tree_edge是一个点到另一个点有边，Edge_value为与之对应的边的权重weigh 方法一：两次深度优先搜索首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度...

树的直径递归队列 dfs bfs 哈希表邻接矩阵

2021-07-18

1 785

题解 | #判断t1树中是否有与t2树拓扑结构完全相同的子树# 来自专栏

思路：题目的主要信息： t1中含有t2的拓扑结构，即t2是t1的子树方法一：先序递归法具体做法：对t1的每个结点递归遍历（先序），寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是t1与t2同步先序遍历，遍历完一个t2或者有不相等的结点为止。 class Solution...

递归子树二叉树

2021-07-18

1 1178

题解 | #最长公共子序列-II# 来自专栏

思路：题目的主要信息：仅存在一个最长公共子序列，不需要去重最长公共子序列为空需要返回"-1"，而不是空序列，最后要变换我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度，若是i与j相等，则该问题可以变成1+dp[i][j]，即最长公...

动态规划字符串公共子序列递归栈

2021-07-18

1 1330

题解 | #寻找第K大# 来自专栏

思路：题目中给到的信息：利用快速排序的思想有重复数字，不用去重，也不用管稳定性与否方法一：重载sort 因为sort使用的是快速排序，因此这种方法勉强算是利用了快排思想。这次要寻找第K大，sort函数默认递增，因此需要将其重载为递减，然后遍历到第k个。 class Solution {...

快速排序递归二分法

2021-07-16

14 1492

题解 | #丢棋子问题# 来自专栏

思路：题目中给到的信息：第0层不会碎某层没有碎，下面的必然不会碎；某层碎了，上面的必然碎要求最坏情况方法一：暴力递归（超时）设count(n,k)计算的是n层楼时且有k个棋子，在最差的情况下需要仍的最少次数。当k=0时，没有棋子，不用仍当n=0时，棋子肯定不会碎，所以count...

丢棋子动态规划递归

2021-07-16

1 691

题解 | #完全二叉树结点数# 来自专栏

思路：最简单的办法莫过于遍历所有的结点，统计个数，但是不管是哪种遍历，时间复杂度都要求至少为O(n)，因为要遍历每一个结点。方法一：遍历法不符合复杂度要求！！！方法二：二分法（利用性质）由此，我们可以从完全二叉树的性质下手：完全二叉树叶子结点只能出现在最下两层最下层的叶子一定集中在左...

二叉树完全二叉树满二叉树递归最大深度

2021-07-16

4 727

题解 | #把二叉树打印成多行# 来自专栏

思路：题目要求将二叉树按行打印，即按层打印，其中每层分开。不难想到，要使用层次遍历，但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue）,事实上，队列中的值大有玄机，让我们一起来看看：当根节点进入队列时，队列长度为1，第一层结点数也为1 若是根...

二叉树层次遍历队列递归非递归

2021-07-15

0 575

题解 | #二叉搜索树的第k个结点# 来自专栏

思路：根据二叉搜索树的性质，其中序遍历是由大到小的，由此仅需要中序遍历找到第k个小的结点即可。中序遍历有两种方式。方法一：递归中序遍历具体做法：另写一函数进行递归中序遍历，设置全局变量count记录遍历了多少个结点，res记录第k个结点。 class Solution { public:...

二叉搜索树递归中序遍历非递归排序

2021-07-15

4 668

题解 | #平衡二叉树# 来自专栏

思路：判断某二叉树是否为平衡二叉树，就需要判断任意一结点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则。则可以相当将问题不断分成子问题，使用递归。方法一：递归判断+递归计算深度具体做法：写两个函数，一个递归遍历二叉树所有结点，判断该结点下的子树是否为平衡二叉树，另一个函...

平衡二叉树递归深度二叉树

2021-07-14

0 587

题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树# 来自专栏

思路：关于搜索二叉树的知识：搜索二叉树左子树上所有值小于根节点，右子树上所有值大于根节点，中序遍历后得到的是一个递增序列。关于完全二叉树的知识：完全二叉树叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树，出现叶子节点以后的节点都是叶子。由此，可用二叉树...

二叉搜索树完全二叉树中序遍历层次遍历队列递归栈

2021-07-14

4 949