684. 冗余连接

题目描述 在本问题中, 树指的是一个连通且无环的无向图。 输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ,满足 u < v,表示连接顶点u 和v的无向图的边。 返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。 示例 1: 输入: [[1,2], [1,3], [2,3]] 输出: [2,3] 解释: 给定的无向图为: 1 / \ 2 – 3 示例 2: 输入: [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4] 解释: 给定的无向图为: 5 – 1 – 2 | | 4 -…

Read more

111. 二叉树的最小深度

题目描述 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最小深度  2. 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DFS 解法1简单的很,我们就用DFS遍历二叉树,声明一个辅助函数用来遍历private int helper(TreeNode node, int depth)。node是当前节点,depth是当前节点深度。如果当前节点是叶节点,就返回depth;如果node左子树非空,就递归遍历左子树求最小深度;如果node右子树非空,就递归遍历右子树求最小深度,然后取左右子树最小深度的min并返回。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – BFS 解法2用队列实现BFS,但是还需要用一个辅助的Map<TreeNode, Integer>记录节点与它的深度。首先从队列出队一个节点,然后从Map取出该节点深度currLevel。每当下一层的节点入队,就将被入队的节点作为key,currLevel+1作为value存入Map中。当发现出队的节点为叶节点时,就终止BFS过程,返回currLevel作为结果。 BFS遍历的好处是,如果首先碰到了叶节点就可以终止遍历过程。而DFS方式需要遍历所有节点才能够知道最小深度。但是最坏情况下BFS和DFS的时间复杂度是一样的,此外BFS还需要用Map存储节点与深度的对应关系,耗费额外的空间;而访问Map还会有一些开销,因此性能并没有DFS好。

Read more

332. 重新安排行程

题目描述 给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。 说明: 1. 如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前 2. 所有的机场都用三个大写字母表示(机场代码)。 3. 假定所有机票至少存在一种合理的行程。 示例 1: 输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] 输出: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”] 示例 2: 输入: [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]] 输出: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”] 解释: 另一种有效的行程是 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]。但是它自然排序更大更靠后。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reconstruct-itinerary 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 首先,我们忽略按照字典顺序排列这一条件,那么这道题本质上求得的是有向图的欧拉路径。 严谨地说,一个连通有向图G有欧拉路径,指存在一个顶点,从它出发,沿着有向边的方向,可以不重复地遍历图中所有的边。 https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98 题目中给定的机场名称是图的顶点,行程是图的边。题目要求重新安排行程,从示例可以看出每个行程都必须用到且只用一次。对应到欧拉路径的定义,每条边都要走到,且不重复。那么,这道题就转化成了给定起点,求一条字典顺序最小的欧拉路径。为了引出解法,我们先放几个例子。 图1展示了一张顶点度数都为偶数的图,首先我们忽略掉按字典顺序输出的条件。我们可以看出,如果顶点度数为偶数,那么我们先从JFK到MUC再回JFK到ATL最后返回JFK,又或是JFK先到ATL再回JFK再去MUC再回JFK,都是合法的路径。如果按照字典顺序输出,我们优先访问字典顺序小的节点ATL即可。因此,我们使用贪心策略,优先访问字典顺序小的顶点。 图2这个例子可以看出,我们别无选择必须先从JFK到NRT再回JFK,最后到达KUL作为终点。如果我们按照字典顺序先到KUL,就进入了“死路”。但是上一个例子我们提到了,优先访问字典顺序小的顶点,那么我们第一次肯定是先到KUL,这就走不通了,那怎么解决呢?当我们采用DFS方式遍历图时,需要将访问到的节点逆序插入到结果集。因此第一个访问到的节点将出现在结果集最后面,而我们是以顺序的方式来查看结果。如果第一个访问的节点是“孤岛节点”,他会出现在结果集的最后。当我们顺序读取结果集时,这种“孤岛节点”是最后遇到的,是图遍历的终点,这样就没有问题了。 我们在图3绘制了算法执行过程,黑色实线表示图的边;红色实实线表示递归调用;绿色虚线表示递归调用返回;数字代表执行顺序;文字表示执行的操作,结果集的数字表示在第几步操作加入的。我们从JFK出发,沿着边到达KUL(因为KUL字典顺序比NRT小),然后KUL没有临接点,将它放入结果集(2),然后从KUL返回到达JFK,注意这个是通过调用栈返回而不是沿着边返回。然后从JFK出发沿着边到达NRT,因为NRT到JFK有返回边,沿着边再回到JFK。此时JFK的两个临接点都访问过了,我们将JFK加入结果集(6)。然后我们从JFK返回到NRT,这是从调用栈返回。然后NRT的临接点都访问过了,我们将NRT加入结果集(8),然后退栈回到JFK。JFK的所有临接点都访问过了,将JFK加入结果集(10),然后退栈,整个流程结束。…

Read more

129. 求根到叶子节点数字之和

题目描述 给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。 例如,从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此,数字总和 = 12 + 13 = 25. 示例 2: 输入: [4,9,0,5,1] 4 / \ 9 0  / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字…

Read more

113. 路径总和 II

题目描述 给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例:给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] https://leetcode-cn.com/problems/path-sum-ii/ 解法1 这道题是“112. 路径总和”的升级版本,在这道题我们需要把所有可能的解都存储下来并返回。为了记录路过的节点,我们使用一个变量List<Integer> path来存储路过的节点的值。我们将每个路过的节点的值都放入path中,如果走到叶节点发现是一条可行的路径(节点值之和等于sum),我们就复制path数组,然后放入到结果变量List<List<Integer>> ans。当从节点返回时,我们需要回溯以保证path变量的正确性。 上面的思路可以使用二叉树的先序遍历来实现。我们用题目给的case来描述执行过程:我们不断地向左走,找到一条路径”5->4->11->7″,path变量的内容依次变为[5], [5, 4], [5, 4, 11], [5, 4, 11, 7]。然后我们发现这条路径的和不等与sum,我们从节点7回溯,path变量从[5,4,11,7]变为[5,4,11],回到节点11走向它的右子树,此时path变量为[5,4,11,2],发现路径和与sum相等,复制path数组的到ans。因为我们需要复用path数组,所以不能直接调用ans.add(path),而是应该调用ans.add(new ArrayList<>(path)),创建path的副本并加入到ans中。 假设我们不考虑path数组复制的过程,那么时间复杂度为O(n)(因为要遍历所有节点),空间复杂度为O(n)(空间为调用栈开销)。

Read more

112. 路径总和

题目描述 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 https://leetcode-cn.com/problems/path-sum/ 解法1 这道题采用DFS就可以实现,我们每路过一个节点,就把节点值从sum中减掉,然后传递给节点的左子树/右子树。当遍历到叶子节点时sum为0,就找到了这么一条路径。由于这条路径可能从当前节点“向左走”也可能“向右走”,他们应该取或的关系。 需要注意的是,有一个case: node = null, sum = 0,它的答案是false,也就是不存在一条路径使得和为0。我一开始写的代码是这样的: 如果这么写,对于上面的case会返回true。我们应该在当前节点为叶子结点时,判定sum是否为0,而不是遇到空节点时再判断,这样就能够使得那个case返回false。下面是正确的代码,时间复杂度和空间复杂度都为O(n):

Read more

257. 二叉树的所有路径

题目描述 给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \ 2 3 \ 5 输出: [“1->2->5”, “1->3”] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3 https://leetcode-cn.com/problems/binary-tree-paths/ 解法1 这道题目很简单,我们只需要先序遍历二叉树,把经过的节点都记录下来就可以了。唯一需要注意的是问题是,我们需要使用“->”连接路过的节点,当遇到叶节点时,我们不应该添加“->”。 我们要遍历全部节点,所以时间复杂度为O(n);当树为链表形态时,栈当深度最深,空间复杂度为O(n)。全部代码如下:

Read more

226. 翻转二叉树

题目描述 翻转一棵二叉树。 示例: 输入: 4 / \ 2 7 / \ / \ 1 3 6 9 输出: 4 / \ 7 2 / \ / \ 9 6 3 1 备注:这个问题是受到 Max Howell 的 原问题 启发的 : 谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。 https://leetcode-cn.com/problems/invert-binary-tree/ 解法1 这道题很简单,我们就把每一层节点的左子节点和右子节点交换,递归执行到叶节点即可。我们在图1绘制了节点交换的执行过程,首先我们交换跟节点4的左右子树,这里的交换不是指节点值的交换,而是引用的交换,这样才能让被交换节点的所有子树也都一同交换。接下来,我们递归交换节点7与2的左右子树。 时间复杂度为O(n),空间复杂度为O(n)。全部代码如下: 解法2 – 待续

Read more

101. 对称二叉树

题目描述 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 说明: 如果你可以运用递归和迭代两种方法解决这个问题,会很加分。 https://leetcode-cn.com/problems/symmetric-tree/ 解法1 为了解决问题,我们先画一个比较general的case来帮助我们思考。我们构建一个4层的对称二叉树,如图1所示。我们可以发现,如果一颗树是对称二叉树,那么它的左子树与右子树是互为镜像的。如图1所示,跟节点root的左子树root.left与右子树root.right互为镜像。因此,我们可以把问题转化为判断两个二叉树是否互为镜像。 为了判断两颗二叉树是否互为镜像,我们创建函数private boolean isMirror(TreeNode node1, TreeNode node2),用来判定两颗二叉树node1与node2是否互为镜像。那我们如何实现这个函数呢? 首先,如果node1与node2都是空,很好理解,他们是镜像的。 如果node1与node2有一个为空,另一个非空,那么肯定不是镜像的。 如果node1与node2都非空,但是node对应的值不想相等,那么也不互为镜像。 如果node1与node2非空,且值相等,那我们还需要递归的判断node1的右子树与node2的左子树互为镜像,且node1的左子树与node2的右子树互为镜像。 我们按照上面的规则递归的判定,直到我们都访问到叶节点后返回我们才能确定两棵树是互为镜像的。如果在递归的过程中发现有不符合上述规则都情况,那么这两棵树就不是镜像的。 下面的代码采用DFS方式判定,我们按照上面4条规则实现了isMirror函数,然后我们把root的左子树与右子树传递给isMirror函数就能够判定整棵树是否是对称的。 解法2 解法2采用另一个比较直观的思路,比较容易理解。我们观察图1,如果树是对称的,那么我们横向读取每一层的节点,都会发现他们是“回文序列”,也就是从左到右读和从右到左读都是一样的。如果有任何一层读起来不是回文序列,那么这棵树就不是对称的! 为了实现按层次遍历,我们使用BFS算法,用一个队列来实现。但是队列没法随机访问,我们在实现时使用数组来模拟队列。如果使用数组的remove方法来出队,会涉及到元素移动,使得时间复杂度达到O(n^2)。因此,我们采用“双缓冲”方法,创建变量queue以及buffer,从queue中读取当前层到节点并访问,将下一层节点放入buffer,然后交换queue与buffer。如果你不清楚二叉树层次变量,可以参考这个。 时间复杂度为O(n),空间复杂度为O(n)。全部代码如下:

Read more

100. 相同的树

题目描述 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true 示例 2: 输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false 示例 3: 输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false https://leetcode-cn.com/problems/same-tree/ 解法1 两棵树相同的定义是结构上相同,且对应位置的值相同。我们首先考虑两颗二叉树,每个二叉树是由3个节点构成的满二叉树。先对比跟节点,如果跟节点的值不相同那么就不用继续比了。如果跟节点的值相同,再分别对比两棵树的左右叶子结点。将上面的过程一般化,如果树由多层的节点构成,我们需要递归的对比左右子树。如果节点缺失了左/右子树,那么另一颗树的相应位置也应该为null。 我们按照上面的说明编写代码,时间复杂度为O(n),空间复杂度为O(n)(树为“线性的“情况下,调用栈的开销),n为节点数量。全部代码如下:

Read more