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

102. 二叉树的层次遍历

题目描述 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 解法1 – BFS 解法1不用多说,在课本中,考研题中经常出现。我们使用队列,将跟节点加入队列,然后出队并访问,再将出队节点的左右子树再一次加入队列……直到队列为空。这种解法很自然,也很容易想到。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – DFS 这道题也可以采用DFS解法,层次其实就是深度,我们记录遍历到每一层级到深度,为每一层级创建List,根据当前深度找到对应的List,然后追加进去。在实现的时候,我们采用先序遍历的,如果采用中序/后序遍历,下面的代码需要略微调整,将if改为while。因为先序遍历能够保证为深度比当前节点浅的所有节点都创建相应的List。而中序/后序遍历会先走到最深的左/右子树,我们必须使用循环为所有层级比当前浅的节点创建对应的List。 DFS理论上会比BFS慢一些,因为存在函数调用与调用栈创建等开销。此外,如果树的层级过高,会有“爆栈”的风险。时间复杂度O(n),空间复杂度O(n)。全部代码如下:

Read more

Leetcode 144/94/145 – 二叉树的前序/中序/后续遍历

题目1描述 给定一个二叉树,返回它的 前序 遍历。  示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ 解法1 – 递归算法 递归解法:定义一个函数private void preorder(TreeNode node, List ans),如果node为空则返回,否则将node.val添加到ans中。然后依次递归调用preorder(node.left, ans)访问node的左子树;递归调用preorder(node.right, ans)访问node的右子树。 时间复杂度O(n),空间复杂度O(n)(递归过程中会创建调用栈,实际上还是有额外空间的),其中n为二叉树节点数量。全部代码如下: 解法2 – 迭代算法 我们创建栈stack,首先将跟节点入栈,然后取出栈顶元素node访问,将node.val加入到结果数组ans中。然后,我们将右子树、左子树依次入栈(如果他们不为空)。因为先序遍历需要依次访问跟节点、左子树、右子树,所以我们需要先将右子树入栈,再将左子树入栈。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 题目2描述 给定一个二叉树,返回它的中序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? https://leetcode-cn.com/problems/binary-tree-inorder-traversal/ 解法1 – 递归算法 和题目1的递归算法类似,我们只需要调整访问node的顺序,使其先递归访问node的左子树;然后将node.val加入到结果数组;最后递归访问node的右子树即可。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – 迭代算法 为了能够将递归算法转化为迭代算法,我们需要模拟调用栈的过程。中序遍历要求最先访问左子树,那我们就创建栈stack,变量node指向当前节点,一直向左下角走,将沿途的节点都加入到stack中,直到走到空节点。当走到空节点时,我们从栈中弹出一个节点并访问,这就是第一个被访问的左子节点。然后我们将node指向node的右子树(node =…

Read more

124. 二叉树中的最大路径和

题目描述 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 6 示例 2: 输入: [-10,9,20,null,null,15,7]   -10    / \   9  20     /  \    15   7 输出: 42 https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/ 解法1 – DFS(超时) 刚遇到题目时没有什么思路,根据题目描述“本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。”,发现这很像图数据结构的DFS算法。 我们可以把树转换为无向图,这通过向TreeNode数据结构添加Parent字段就能够实现。这样,每个节点有三个临接点分别是左子树、右子树、父节点。 我们从树中寻找val大于0的节点作为DFS的起点,从所有的起点出发遍历完这棵树,肯定能找到包含答案的路径。我们累积走过的每一个定点的值,用当前累积的值更新全局变量result,result就存放了最终的答案。 很遗憾,上面的方法虽然能够找到正确的答案,但是效率太低。我一时也没有找到这种方法的优化思路,先记录下来。 解法2 方法2来自于该题目的评论区。思路是:节点n向父节点汇报以下三者中的最大值;如果节点n是叶节点则仅汇报节点n自身的值。 节点n的值 节点n的值+节点n左子树汇报的值 节点n的值+节点n右子树汇报的值 我们以图2为例,红色字体给出的是节点向其父节点按照上述规则汇报的值。注意,图2与图1不相同。 有了上面的图,我们把图中每个顶点“臆想”成该顶点就是整颗树的根节点,而忽略掉该节点之上的其他节点。然后我们对每个“臆想”的根节点,按照以下规则计算出的最大值。 根节点的值 根节点的值+左子树汇报的值 根节点的值+右子树汇报的值 根节点的值+左子树汇报的值+右子树汇报的值 因为我们把每个节点“臆想”成根节点,我们才会有上面规则的第4条。需要注意的是,该问题的解并不一定来源于整颗树的根节点。我们想个反例,把图2的根节点5的值调整为-∞,那么解应该来源于节点8….

Read more

109. 有序链表转换二叉搜索树

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10, -3, 0, 5, 9], 一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5 https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/ 解法1 二叉搜索树(BST)是一种特殊的二叉树,他满足左子树的全部元素都小于根节点,右子树的全部元素都大于根节点。题目另外要求生成的平衡的BST,意味着在上面的基础上又添加了新条件:左右子树高度差的绝对值不超过1。 首先给定的链表是有序的,加上BST本身的特性会使我们联想到二分查找的思想。根据有序列表构建BST我们可以使用类似于二分查找的思路,用中心元素将链表划分为两部分,左半部分都小于中心元素、右半部分都大于中心元素。 采用链表作为数据结构,不容易实现随机访问。为了能够快速的获取中心元素,我们首先将链表转换为数组。我们取数组长度的一半作为中心元素的索引。中心元素作为二叉树的根节点,将左半部分与右半部分以相同的方式处理继续构建左子树与右子树。直到左半部分或右半部分没有元素时,构建过程停止。 下面以题目以“[-10, -3, 0, 5, 9]”为例,构建BST。下面的图片给出了两颗BST,他们都是合法的,但我们的处理逻辑仅能够产生左边的形态。 我们列举BST的构建过程来说明,为什么我们的逻辑只能够产生左边的形态。首先,说明下我们采用的边界都是左闭右开的形式。arr=[-10, -3, 0, 5, 9]。|arr|=5, mid = (0+5)/2 = 2,取arr[2]=0作为中间元素,左半部分为[-10, -3],右半部分为[5, 9]。我们继续利用左半部分构建根节点0的左子树。计算|[-10, -3]| = 2,mid = (0+2)/2 = 1,取arr[1]=-3作为根节点。我们可以看到,因为左子树仅有两个元素,按照我们mid=(左边界索引+右边界索引)/2的处理方式会将第二个元素-3作为子树的根节点,而不是-10作为根节点。…

Read more