Leetcode按题目类型总结(八)

二叉树

Posted by Jingming on November 15, 2017

所有代码详见:https://github.com/jingminglake/Leetcode

总体思路

树的题目,首先考虑树为空的特殊处理。树的题目类型大概有:

  • 树的遍历

    前序、中序、后序、层序等。

  • 树的构造

    构造树、合并树等。

  • 树的特殊结点查找

    找前驱后继等

  • 树的路径

    路径分为可以有兄弟结点和不可以有兄弟结点的路径,只要是路径题目,就考虑路径的开头和结尾,并考虑以具体结点为开头或者结尾的情况有多少种,以便计算时间复杂度。 二叉树的一个特点:从叶子结点到根结点有且只有一条路径。

  • 几个类似的等价的解法的题目

中序搜索二叉树,求二叉树的中序后继、前驱, 删除二叉树的结点,设计二叉树的中序迭代器。

具体题目

144. Binary Tree Preorder Traversal

题意:前序遍历二叉树。

:递归解法:先遍历根元素,接下来就是递归到左右子树的递归。

非递归解法:遍历的意思,就是可以把该元素打印出来。问题难点在于,先要打印完左孩子,才能打印右孩子,先遍历左孩子后当前结点会丢失,需要使用数据结构保存。 使用什么结构呢?由于树是一种递归型的结构,遍历左孩子的过程中,左孩子对自己的左孩子也有相同的处理方式,所以使用栈,每次访问到的结点都是作为栈顶,虽然后来但是先处理。

方法一:从root开始,在该节点不为空或者栈不为空的时候,进行遍历:首先不断向左访问直到最左边的孩子,访问过程中的结点全部压栈, 直到最左边的孩子后,意味着左侧的孩子全部打印了,此时应该处理栈顶元素了,弹出一个元素(如果栈不为空) 那么同样逻辑(访问所有左孩子)处理该元素的右孩子,然后继续进行栈处理。

方法二:把元素的访问和打印操作分开,访问意味着要进行当前结点的打印以及处理他的左右孩子, 例如,一开始就是对root进行访问,对root进行访问后栈状态是:{访问root的右孩子,访问root的左孩子,打印root}。

http://blog.csdn.net/gatieme/article/details/51163010

94. Binary Tree Inorder Traversal

题意:中序遍历二叉树。

:递归解法:空结点直接返回,只有一个结点,那么就直接打印,否则,先解决左孩子的子问题,然后打印自己,再解决右孩子的子问题。

非递归解法, 方法一:访问左孩子的时候,不进行打印就进行入栈操作,所有左孩子压栈后,打印栈顶结点,然后对栈顶结点的右孩子做相同处理。

方法二:把元素的访问和打印操作分开,一开始就是对root进行访问,对root进行访问后栈状态是:{访问root的右孩子,打印root,访问root的左孩子}。

145. Binary Tree Postorder Traversal

题意:后序遍历二叉树。

:递归解法:空结点直接返回,只有一个结点,那么就直接打印,否则,先解决左孩子的子问题,然后解决右孩子的子问题,最后打印自己。

非递归解法:方法一:修改先序遍历的程序。先序遍历是根-左-右,后序遍历是左-右-根。只需要将先序遍历的程序改为根-右-左,然后只需要反转,就可以得到左-右-根。

方法二:也需要先把左孩子全部入栈,问题是打印结点的时机:打印完右子树才能打印根,也就是说,对栈顶的处理是对栈顶的右孩子做相似的处理(此时不弹栈顶),但是存在另外一种情况是,有时候栈顶需要弹出来,例如遇到了基本情况发现栈顶元素没有左右孩子,或者是最后一次打印的元素是栈顶元素的右孩子。 那么,对于栈顶处理的分辨技巧就是使用变量记录下最后一个被打印的点:弹栈的时候对于其右结点进行判断,如果右结点为空,或者右结点是上一次打印过的结点,那么栈顶要被打印,且栈顶的右孩子不再做同样处理了,因为已经处理过了:栈顶打印之后,一个是要更新最后打印的结点为栈顶,另一个是要把当前cur元素置nullptr表示以后不需要考虑cur的左孩子压栈的问题。 如果两个条件都不符合,那么直接对栈顶右孩子进行同样的处理。

小结:后序遍历的特点就是:右孩子一旦要打印,那么下一个打印结点只能是他的父节点。

方法三:把元素的访问和打印操作分开,访问意味着要进行当前结点的打印以及处理他的左右孩子, 例如,一开始就是对root进行访问,对root进行访问后栈状态是:{打印root,访问root的右孩子,访问root的左孩子}。

687. Longest Univalue Path

题意:找出二叉树中相同数字最长链的长度。最长链可以经过父节点到兄弟结点。

:分治法。分为两种情况,一种是最长链不经过root,那么答案在root的左子树或者右子树的子问题之中的较大者,一种是root必须连接左右子树。两种情况计算出的最大值就是答案。

f(root) = max {g(root), h(root)} ,其中

g(root) = max{ f(root->left), f(root->right) },

h(root) = max {g(root->left), g(root->right)} + 1(if root->left->val == root->val == root->right->val)。

每次求左子树的结果和右子树的结果。之后看root和左子树的值以及右子树的值是否相同,如果相同,那么结果+1,然后看当前值做连接左右的最大长度是否可以更新最大值(对每个点进行考虑后选出来的最大值)。如果当前结点值既不等于左孩子的值,也不等于右孩子的值,说明当前结点值作为链的结果是0。

235. Lowest Common Ancestor of a Binary Search Tree

题意:求搜索二叉树中两个点p和q的最低公共祖先。

:从root开始,如果当前访问结点大小如果介于p和q之间,直接返回,如果比两者都大,那么问题递归到左子树,如果比两者都小,就递归到右子树。

此题的启发:(1)对于树的问题,一定要看清是什么树,对于特殊的例如搜索二叉树,那么就要使用特殊的搜索方法。

(2)要考虑结果的性质,也就是看结果会落入哪些情况。此题,如果经过细心观察,可以发现,如果树上的一个结点大小介于p和q之间,那么他必定就是最低公共祖先。

PS.此题技巧是不用关心p和q谁大,只需要知道root是不是比两个都大或都小,然后剩下的就直接返回root就行了。

236. Lowest Common Ancestor of a Binary Tree

题意:此题和235题不一样之处在于,是一棵普通的二叉树。

:如果pq两个结点分别处于某结点为根的树的两侧,那么该结点就是最低公共祖先。这一点比较难想到。

分治法解决,首先考虑分解,看根,如果根是p或者q,那么作为答案返回,否则根的结果应该是与自己的左子树的lca的答案一致,或者是与右子树的lca的答案一致,其中如果左右子树的lca分别是p和q,那么说明根自己是答案。

在来考虑基本情况:(1)树为空,返回空作为lca答案;

(2)树只有一个节点,如果该节点是p或q,则返回p或q作为lca答案,否则返回空作为lca答案;

(3)树有两个或三个节点,如果根是p或q,那么p或q就是lca结果;如果根不是,那么看子节点,也就是递归到情况1和2,也就是说,子树的lca答案一定要发给父结点做参考。

总结:根是答案有两种情况:(1)根是p或者是q,(2)pq的位置位于根的两侧。 在当前树中,如果先找到p,那么就直接返回p,如果先找到q,那就直接返回q。对于root,只存在如下情况:一个是p或q和root相等,那么直接返回作为结果就行了;另一个是root和p,q都不等,那么问题递归为左子树中找和右子树中找,如果两个都找到了,说明p和q是在root的两侧,那么返回root。否则,找不到的为空,返回其中一个找到的就可以了。

PS. 所谓递归,就是先将大问题变为子问题,然后将分解过程形成一种逻辑上的结构,这种结构适合放在数据结构栈里面,直到遇到基本情况的时候,这种结构开始消解,结构为空的时候自然得出答案。也就是说,无需关心栈具体长什么样,而是只要相信栈结束后就能得到要求的解就行,而且要知道的就是,时间看起来是比N变多了的,但是有的时候并不影响复杂度的量级,而是要根据公式来具体计算。对于本题,递归公式为 T(n) = 2 T(n / 2) + O(1),根据画分治的树或者数学递推式计算就可以知道, T(n) = 1 + 2 + 4 + … + n,根据等比公式,结果为 2n -1,也就是时间复杂度是O(n)。 对于递归,真正要关心的就是基本情况以及如何对问题进行分解。

总结:一个父结点解决不了的问题,就交给子结点去解决,但是子结点的答案只能作为父结点的参考;与此同时,父结点还要将自己的答案交给它的父结点去参考。

617. Merge Two Binary Trees

题意:是merge两个二叉树。

:递归,先合并自己,然后递归合并左右子树。

启发:看到树的题目,首先想能不能递归解决,能的话,就考虑递归的出口,也就是假设子树已经解决了问题了,接下来看自己如何解决。

606. Construct String from Binary Tree

题意:是先序的遍历树,把遍历的路径构建特殊字符串:把左右子树用括号分别扩起来。

:递归的先序,其他不要想的太多。树的问题,第一反应就是能否递归解决。

注意:如果右孩子结点不为空,而左孩子结点为空时候,需要加入多余的”()”。

536. Construct Binary Tree from String

题意:由606题生成的串还原回原来的树。

:递归。分析下当前字符串,发现字符串格式为rootVal+(左子树)+(右子树)。所以现在需要一个变量cnt来记录左括号的数量(类似括号匹配时候的处理),遇到左括号,cnt+1,遇到右括号,cnt-1。先把rootVal部分找到,然后向后找,如果cnt为0,说明是左孩子或者是右孩子,这时候需要保存第一个左括号的起始位置,在处理完左子树之后,将标记移动到第二个左括号的起始位置,就可以分辨出右子树。也就是说,同时处理左右孩子,就可以区分开左右孩子。

98. Validate Binary Search Tree

题意:验证一棵二叉树是不是二叉搜索树。

:二叉搜索树意味着左右子树是二叉树,且左子树始终小于根,小于右子树。

方法一:使用二叉搜索树的性质,中序遍历是有序的,进行一次中序遍历,遍历时候,记录前一步的值,如果下一个访问的值比前一步的值小或等于,那么说明不是二叉搜索树。 prev值初始化为INT64_MIN。

使用递归遍历的时候,其实可以计算每个点为根的二叉树是不是搜索树,它的左右子树均为二叉搜索树是必要条件。

方法二:进行前序遍历,如果是二叉搜索树,那么当前处理值对左右子树来说,意味着:(1)它比所有左子树的值大;(2)它比所有右子树的值小。

这样,进行前序遍历,如果所有的点都满足落入当前的最大值最小值范围内,那么就符合二叉搜索树的要求。一开始的最小值是INT64_MIN,最大值是INT64_MAX。

方法三:使用后序遍历,每个点扫描的时候,要看是不是比左子树的最大值大以及比右子树的最小值小。每次结点的计算,都要返回当前结点为根子树的最小值,最大值以及当前子树是否是BST,递归的基本情况是:空节点的最小值为INT64_MIN,最大值是INT64_MAX。 一个点如果满足条件之后,要对结点的最小最大值进行更新,也就是左子树的最小值和右子树的最大值,有例外就是左右子树为空的时候,最小(大)值要更新为结点的值。

501. Find Mode in Binary Search Tree

题意:找出BST中的所有众数。

:如果是普通遍历,加hash表,那么相当于是O(n)时间、空间,但是没有使用到BST的性质。利用BST性质进行中序遍历,我们知道可以从小到大依次遍历,所以使用中序遍历,每次遍历的值看等不等于prev,如果相等,那么当前值的数量统计cnt加1,然后看cnt是不是比最大cnt大,如果大的话,那么把结果数组清空,如果等于最大cnt,那么加入结果数组。

449.Serialize and Deserialize BST

题意:序列化BST

:序列化的要点: 序列化的信息需要保证是二叉树的一种唯一表达的形式。 需要深刻理解二叉树的唯一形式,也就是二叉树的空节点信息不能忽略,而要看作“#”。

此外,此题区别于297题在于,需要充分利用BST的特点,也就是比所有左孩子大,比所有右孩子小。因此,全搬297的解法,虽可行但不是最优的。

可以对297的方法一进行改进(解法时间总体复杂度不会变化,而空间复杂度可以减小)。

和297方法一不同之处在于:二叉树的形式可以使用先序遍历+中序遍历(默认就有,无需记录)来唯一表达。也就是说,序列中无需记录“#”空节点,而只需要记录先序遍历结果(更加简短)。

中序遍历结果(就是升序)是已知的,可以在树还原(反序列化)过程中可以加以利用。 具体来说,如何知道空子树的存在?

解法是,还原的先序遍历数组的时候,递归函数保持一个临时的最大值和最小值,如果当前扫描的值不介于函数规定的最大最小值之间,说明该结点不属于该子树,所以直接返回空结点,否则创建该结点,然后左子树的最大值修改为当前值,右子树最小值修改为当前值。

PS. (1) int与string,char型之间的转换技巧 int转string,例如:123转成“123”,使用to_string(123)。 string转int,例如将123转“123”,使用stoi(“123”)。 char*转int,例如char *c = ‘1’转1,使用atoi(c),如果是string数组的下标访问形式,那么要加.c_str(),例如:atoi(s[8].c_str())。 char转int,例如‘1’转1, 直接使用’1’ - ‘0’即可,对于string数组的下标访问形式也是一样,例如s[8] - ‘0’。

(2) c++的split,参考https://github.com/jingminglake/Practice/blob/master/split/split.cpp

662. Maximum Width of Binary Tree

题意:求树中最远的两个结点,从横向距离(宽)来看。

:是带层次的宽搜,要注意的是,将树当作满树结构来看,也就是说,每个结点其实都是可以按满树进行编码的。入队的时候,要加入结点的编码信息,左孩子是2i, 右孩子是 2i+1。

层次宽搜,每次把该层第一个元素的下标取出来,然后扫描的时候,把该层最右边的下标也取出来,然后就能知道当前层的宽度。

545. Boundary of Binary Tree

题意:求树的逆时针边界组成的数组,即[左边界、叶子、右边界]。

:一种解题思路:先理解左右边界:左边界就是除了叶子结点以外的最左边的路径,也就是有左孩子且左孩子不为叶子的时候就向左走,并沿途记下结点,然后如果没有左孩子,那么向右孩子走,如果右孩子不是叶子,则记下来,然后沿着右孩子的左孩子走。也就是一个遇到叶子结点就停止的一直沿着最左边走的过程。

同理,右边界是一个遇到叶子结点就停止的一直沿着最右边走的过程。

叶子结点可以使用先序遍历来找。

所以,只需要三遍扫描就可以得出答案。注意的是一开始的root为非叶子时候,一开始就要加入结果中,然后在找左边界右边界的过程中,只需要处理左右孩子即可,这样root就不会重复算。而root作为叶子时候,不需要先加入,因为后面处理叶子时候,会从root开始算。

270. Closest Binary Search Tree Value

题意:求二叉搜索树中离target最近的结点的值。

:解题的关键在于理解如果target比root值大,那么root的左子树不用在考虑了,因为root肯定比左子树大,target又比root大,所以结果肯定是root或者是root的右子树中。反之亦然。

非递归解法:使用循环进行二叉树搜索,root值比target大的时候,向右边搜索,反之,向左搜索。然后沿途更新离target最近的值,最终搜索到空结点的时候,返回最近的值。

递归解法:root值比target大的时候,结果在自己和右子树子问题求出的结果中离target最近的那个,反之亦然。难点是递归时候,在树为空的时候,该如何返回。方法是自己定义helper函数,在空的时候,返回int64的最大值。

101. Symmetric Tree

题意:验证二叉树是不是对称的。

:二叉树是对称的意味着根的左子树和右子树是对称的,问题转化为比较两棵树的对称性。两棵树对称,首先要求两棵树的根的值相等,同时要求第一棵树的左子树和第二棵树的右子树是对称的,第一棵树的右子树和第二棵树的左子树是对称的。所以,可以使用递归解法,基本情况就是两棵树只有一个结点,且值相等,那么是对称的。

333. Largest BST Subtree

题意:给出一个二叉树(不一定是BST),求其中有最大结点数量的BST。follow up是要求O(n)时间。

:此题可以分解为两个功能,一个是计算子结点总数,一个是判断是否是BST。常规解法就是,先后序遍历一遍计算出所有子节点数,耗时O(n),遍历期间内对每个结点为根的子树使用中序遍历判断是否是BST,消耗O(n),总时间为O(n^2)。

如果要更快速,那么需要O(n)时间求出所有结点为根的子树是不是BST,使用以前的中序遍历是做不到的,因为那样需要从每个点出发计算。

O(n)的方法就是要利用递归思想,只需要O(1)时间判断一个结点为根的子树是不是BST,那就是后序遍历,判断方法就是左、右子树都必须是BST且左子树中的最大值要小于根节点的值且右子树中的最小值要大于根节点的值。 既然都是后序遍历,那么可以将两个函数融合在一起进行一次遍历。每次返回四个值: 子树的最大值、最小值、是否是BST、以及子树的结点个数。可以新建一个类来作为返回类型。

106. Construct Binary Tree from Inorder and Postorder Traversal

题意:是给出中序和后序序列,来构建二叉树。

:此题是分治法,对于中序和后序都要使用start和end来标记下标,然后把问题切分为子问题,子问题中序和后序也是相对应的,也就是中序和后序start到end的大小是一样的。每次切分的契机就是后序序列的最后一个元素。

PS.可以使用hashmap来快速得出中序数组中的元素到下标。构建hash只需要扫描一次中序数组,以后就不需要每次都O(n)的去找了。

114. Flatten Binary Tree to Linked List

题意:将二叉树翻转为先序遍历的链表,只使用结点的右指针,空间复杂度要求为O(1)。

:此题解题套路就是遍历时候保持一个全局指针,指向当前访问结点翻转为链表后的链表头。

按先序遍历来遍历,这样每次遍历到的结点都是当前链表的最后一个结点,加入链表尾部即可。注意的是:在构建链表的过程中,先序遍历的右子树递归结构的初始值会被改变,因此,在被破坏之前记录下来,然后使用备份的值就行了。

也可以需要使用先遍历右子树的后序遍历(右左根)。后序遍历首先把root右子树(假设根为r)变成链表l,然后prev此时代表r的右子树的根。此时后序遍历下一个要访问的是root左子树中最右下的结点,该结点的right会指向l链表。也就是说,每个下一个后序遍历的结点的right指向前面遍历所有的结点组成的链表。这种方法和先序没有太大区别,只是递归结构初始值不会被破坏。

PS. 构建链表的期间不要忘了将访问结点左子树置空。

426. Convert Binary Search Tree to Sorted Doubly Linked List

题意:将BST按顺序(也就是中序)变成双向循环链表,并返回链表头,也就是BST里面的最小的值。

: 方法一:分治法。先将左右子树变为双向循环链表,然后与根进行拼接。基本情况需要处理,左右子树都不为空,一个为空,都为空的情况。

方法二:由于是BST,所以,双向循环链表的头尾,应该是容易得到的。首先,进行中序遍历,使用假头结点的方法,并使用全局的尾指针技巧(参考114题),就可以把BST转为双向链表,最后,使用假头节点和尾指针对双向链表进行收尾相连,形成双向循环链表。

285. Inorder Successor in BST

题意:BST给出root和一个结点p,求p的中序后继。

:一种解法是:如果p有右孩子,那么找出p右孩子的最左下边的子结点就可以;

如果p没有右孩子:如果p作为父节点的左孩子的时候,那么p的后继是他的父节点;如果p作为父节点的右孩子,那么p的后继是沿着父节点向上走的路径(此路径是唯一的)上的第一个作为左孩子的结点的父节点。

具体解法就是从root开始找,如果cur的值比p的值小,说明cur应该变大,cur向右走;如果cur的值比p的值大,说明cur应该变小,cur向左走;如果cur的值等于p的值,那么cur置为空(走到右孩子),结束循环。每次向左走之前要记录下当前比p大的结点,向右走则不更新记录。这么做的原因就是记录下查找路径中当前结点中的作为左孩子的结点的父节点。 这么说来,当p作为左孩子时候,其父节点也相当于查找路径上最后一个有左孩子的父节点。

方法二:直接从root开始找,如果当前值比p的值小,或者相等,那么向右走。如果右已经为空了,说明没有比p值大的,也就是没有后继,那么返回null。否则,已经知道答案肯定在当前结点的左子树中了,那么对左子树进行递归的查找,如果左边求出的结果确实比p值小,那么就是结果,否则还是左子树的根来作为结果。

方法三:直接从root开始找,如果当前值比p的值小,或者相等,那么向右走,否则向左走,并记录下当前的点,目的是记录下最后一个向左走的结点,也就是p的后继。相等时候向右走,然后比p大,然后向左走一直走到空结束。

173. Binary Search Tree Iterator

题意:为BST设计O(1)时间复杂度的中序next(), hasNext()的接口,空间复杂度要求为O(h)。

:空间复杂度为O(h),所以也意味着不能使用hash表,只能使用其他数据结构,存储的信息是树高路径。使用stack来存储root沿左边走的路径,直到空停止,此时栈顶元素就是最小值了,如果栈顶元素被取出来,那么将沿它右孩子的左边路径访问并存储到栈上。栈不为空,说明hasNext。

PS.设计迭代器的题目都是使用迭代来解。

前序遍历和中序遍历使用栈的区别在于,一个是元素入栈的前一刻打印元素,一个是在出栈后一刻立即打印。

平摊后时间复杂度为O(1) : https://stackoverflow.com/questions/12882424/in-order-traversal-complexity-in-a-binary-search-tree-using-iterators

116. Populating Next Right Pointers in Each Node

题意:完全二叉树,需要将每层的左结点指向右结点。空间复杂度要求为O(1)。

:此题空间复杂度要求为O(1),所以不能使用queue来层序遍历,也不能使用递归,因为递归也存在调用栈。所以此题解法只能是沿着树进行遍历。

遍历时候,按层序遍历。每一层把下一层的横向走法接通。 先沿着左子树走,每一层建立新的指针向右横着走(上一步会把向右走的接通)接通下一层的横的部分。沿着左子树走完。

PS.(1)最后一层链接好的结点遍历的时候,下一层不能继续链接了,有两种判断方式,第一种就是连接时候先判断有没有孩子,第二种是在头结点的时候,就看当前层的下一层是否为空。

(2)技巧是对一个实在的结点,可以使用不止一个指针,来代表不同含义,此题可以使用一个指针指向root来保证往左走得到每次的头节点,使用另外一个指针指向头节点,每次向next方向走。

117. Populating Next Right Pointers in Each Node II

题意:和116唯一不同之处在于不是完全二叉树。

:此题思路是,一层一层的访问,每一层访问的时候是上层是已经被建立好可以直接使用(root一层只有一个结点,看做建立好的),根据上一层构建当前层, 然后当前层遍历的时候建立好下一层,然后切换到下一层继续遍历。

建立dummy结点,第一层是root,如果root的左孩子存在,则加到dummy链表最后面(使用链表尾插法,多一个last指针),如果右孩子存在,那么加入dummy最后面。root的next为空,说明结束root所在层的访问。然后,下一层的起点就是dummy的next了。然后同理的构建第3层的链表。记得每次都要把dummy后面的链表给剥离出来,即dummy.next = nullptr。

124. Binary Tree Maximum Path Sum

题意:求二叉树中最大路径和,路径允许经过root。

:允许经过root的路径的意思是:一个点可以把自己和自己俩孩子连起来表示一条路径。

对每个结点的考虑,必须经过自己的且自己作为子树根的最大路径和。此时对他的孩子考虑,孩子自己考虑也是最大路径,所以有两种情况: (1)把自己当作链接左右桥梁来看:选两个孩子(只要孩子最大和是正数)通过自己。

(2)考虑把自己链接到上一层。即使两个孩子为正,也只选择一个最大的孩子和自己做为当前结点的max。如果两个孩子都小于0,那么都不选。

此题理解的关键:当前结点所在子树问题传回上一层的时候,就是默认把自己连接到上一层了,不可能存在自己当作桥梁还传到上一层的情况。

366. Find Leaves of Binary Tree

题意:给出二叉树的root结点,模拟叶子节点删除的顺序,每次作为一组,直到所有点被删光。

:此题一开始准备使用左右子树结果按顺序合并,但是操作实在是麻烦。答案的做法是,计算每个结点自己子树的高度,如果高度相等的结点,那么就作为一层即可。做法就是,每次遇到新的高度,那么加一组,否则就在当前高度的那一组把该元素加上去。

156. Binary Tree Upside Down

题意:首先,树形状是有限制的:每个结点的右孩子必然存在和他同level的兄弟结点(也就是共享父结点的左孩子),要不就为空结点。翻转规则是对一个存在右兄弟的结点:他的父节点成为他的右孩子,他的右兄弟成为他的左孩子。

:因为root的左孩子必有右兄弟,所以需要沿root左边走,对每个左孩子进行操作,发现是递归的,把左子树的子问题解决后,当前root的右孩子赋给左孩子的作为左孩子,root自身作为左孩子的右孩子,注意此时root已经是叶子了,所以左右孩子全部置为null,然后返回翻转左孩子后的新节点。递归的出口是:root为空,或者root左右节点都为空,返回root。

653. Two Sum IV - Input is a BST

题意:此题在BST中找2Sum。

:此题解法并没有用到BST的中序有序的性质,反而是用了BST的元素不重复的性质,所以只需要遍历一遍BST,遍历过程中使用hash记录下已经访问的结点,然后看target - val是否在hash表中就可以了。

314. Binary Tree Vertical Order Traversal

题意:垂直的遍历二叉树。

:此题一定要使用层序遍历,然后把值放入到对应的每一垂直层。现在问题是如何找垂直层。垂直层的找法是root是0,然后往左走一步减一,往右走一步加1。现在问题变为处理下标是负数的情况:两种方法:一种是先遍历一遍求出最左和最右值,然后每次减去最小值得出大于等于0的数;另一种方法更加简单,那就是使用没有正负数区别,而且和数组原理一样的map,先把结果存入map,然后把map还原成数组。此题map要使用treemap,因为要排序。

298. Binary Tree Longest Consecutive Sequence

题意:求二叉树中,最长相邻连续的序列,连续是指严格的1,2,3,…递增,相邻是指结点之间是连通的,且此题序列要求是严格从父节点到子节点的,不能由子节点经父节点在到兄弟节点。

:此题使用dfs求解。dfs过程中,使用全局变量记录下最长的序列,然后,每层记录当前的最大值(这个值不能使用引用,要使用副本来保持往下传的是一致的),这个值在搜索过程中如果中断,需要重新置为1,表示从这个结点作为开头继续向下搜索。 下一层的target就是上一层的root->val + 1,一旦下一层结点值等于target,那么当前层最大值就加1。 这种树中考虑局部,全局解的问题应该使用dfs,或者使用后序遍历辅助函数。

549. Binary Tree Longest Consecutive Sequence II

题意:与298题相比,此题既可以是递增相邻序列,也可以是递减相邻序列,另外,可以连接左右子树。

:此题处理局部最优解比较麻烦。比较简洁的思路就是递归。递归时候,返回两个值,一个是局部的递增最优,一个是局部的递增的,注意,这里的局部是指一定要考虑当前结点。 然后,使用全局变量保存最大值。递归使用后序遍历,知道两个子节点的局部最优解之后,看自己能不能更新局部最优解,以及全局最优解。返回自己的局部最优解。

PS.1.全局最优解看原来全局最优解大,还是局部两个变量加起来减1(减1是因为两个局部都考虑了当前结点)哪个大。因为两个局部变量拼起来刚好是有序的。

2.每层处理要考虑左右孩子不为空,而且,左孩子处理后,右孩子在处理的时候,当前局部变量应该要和之前孩子处理之后的结果进行比较。

572. Subtree of Another Tree

题意:检查一棵树s是不是另一棵树t的子树。树中元素可以重复。

:此题思路是分治。检查t树是不是和s树一样,如果一样,那么返回true,如果不一样,那么看t的左子树或者t的右子树哪一个和另一个树一样,有一个一样就返回true。 检查两棵树是否一样,也是使用分治法。注意的是,比较完时候,如果一方结点不为空,那么也说明不是相同的树。

779. K-th Symbol in Grammar

题意:给出N表示扩展了N次,K表示第N次里面的第K位,求K位是0还是1,扩展的方式是从0开始,0变01,1变10。

:此题非常有意思,只要将扩展的按二叉树来看,发现就是一颗满二叉树。所以这里利用一个规律,那就是如果K是偶数,那么说明他是父节点的右孩子,反之是左孩子,这样我们通过递归父节点是0还是1,就能反推自己是0还是1。 来看一下K的分布。 1 1 2 1 2 3 4 1 2 3 4 5 6 7 8 … 求第N层的K的问题,K为奇数时候可以递归到父节点的 (K + 1) /2, K为偶数时候推到父节点的K/ 2。

652. Find Duplicate Subtrees

题意:求解二叉树中重复子树的根节点。

:判断重复子树:就是将二叉树的每个点进行序列化,如果序列化出来的串是一致的,就说明重复。 序列化具体操作方法就是指按照某种遍历顺序,结合额外信息组成的唯一的串。 此题计算每个结点的序列化串,然后使用hash记录串出现次数,如果出现超过两次,那么就说明出现了重复子树。

776. Split BST

题意:实现BST的split操作,按节点值V将BST分为两颗子BST树(第一棵小于等于V,第二颗大于V)。

:使用递归。如果V比root值小,那么说明root以及root的右子树可以作为一个部分,也就是可以作为分裂节点V的第二颗树T2的右子树存在,那么接下来就是对root的左子树进行考虑了,这是一个递归的过程,也就是说,root左子树将分裂成两棵树,然后其中的第二颗树(比V大的部分)作为上一步第二颗树T2的左子树存在,左树(比V小的部分)单独出来,作为上一步分裂节点的左子树。 同理,在V比root值大的时候,那么也是相同的思路来处理。

再来看基本情况,那就是BST只有一个节点,那么将根据节点值比较的大小分为两个树,一个为空树,另一个为节点自己。 V等于root值的时候,根据题意,root属于第一颗树。

272. Closest Binary Search Tree Value II

题意:找出BST里面最接近x的k个数。

:(1)暴力求解:inorder扫描,然后将数加入最大堆,最大堆的大小控制在小于k,里面元素存的是pair,pair第一个元素表示距离x的距离,第二个元素是结点大小,扫描一遍后得出答案,消耗时间O(nlogk)。

(2)可以使用BST中序是有序的性质,维持一个deque,然后在不足大小k的时候,直接加入deque尾,之后,如果在遇到值距离比deque的头距离x更近的,那么deque头弹出,然后在尾将该元素放入,这么做的原理就是,deque的头有两种情况,一种是他落在x的右边,此时当前扫描值一定也在x的右边,且不可能入选;另一种是他落在x的左边,此时扫描值可能在x左或者在x右,如果在x左,那么queue头后面的元素都只可能比头距离更靠近x,所以要弹的话就弹头;如果在x右,如果当前值比头更加靠近,作图发现,也是需要弹头,如果比头远,那么直接忽略。 此方法时间复杂度O(n)。原理其实是滑动窗口,滑动窗口一开始包含所有的候选者,然后之后可以替换的就是窗口中最不符合条件的,这样最终窗口剩下的必然就是结果。

(3)使用额外O(n)空间,然后使用两头双指针,去除离x较远的n-k个元素,时间也是O(n)。

(4)使用两个中序迭代器,一个是最接近x且比x小的,另一个是最接近x的最大的,空间降到O(logn),然后向两边扩展,扩展到k个数即可。 此思路的原理就是logn的时间找到最接近x的两个元素,然后使用k的时间找出k个数,消耗时间为O(logn + k)。

437. Path Sum III

题意:给出一颗整数(有正有负)二叉树和一个整数target,现在求二叉树里面路径和等于target的路径有多少。路径不必须要经过root或叶子,只要是连续且向下的(不能有兄弟结点的这种)就可以。

:先看一颗二叉树有多少条路径,如果路径要经过root和叶子,那么路径数和叶子树相同,因为叶子到root只有唯一一条路径。

现在是root到叶子上组合的选两个点就可以组成路径,假设n为叶子结点总数,如果二叉树是极度不平衡的,也就是一条线的时候,时间复杂度是O(n^2),因为从n个里面选出两个就可以得到一个路径。

如果二叉树是平衡的,也就是高度为logn时候,root可以和任意其他结点组成一条路径,就是n-1条路径,而root的左孩子可以同样的方式组成n/2 - 1条路径,右孩子也一样,所以第二层是(n / 2 - 1)* 2 = n,每层都是n,且树高为logn,也就是说,时间复杂度是O(n logn)。 此题如果使用暴力求解,那么时间复杂度是O(n^2),最好情况下,时间复杂度也是nlogn。

方法一:暴力求解,也就是分治法。问题解记做f(root),可以拆分为两个子问题,一个是经过root的路径的解,一个是不经过root的路径的解。假设必须经过root的这种解法叫做g(root),那么不经过root的解法,其实等价于f(root->left) + f(root->right)。所以问题拆解为三个子问题的和。其中g(root)解法经过之前的分析知道,其实它的子节点数就是路径数,计算每个节点和root的距离就可以了,可以使用DFS,每一步都可以使用父节点的和加上自己,然后看自己距离root是否是target,如果是,那么cnt++,还有一种思路,就是父节点将target的剩余传给自己,如果自己可以把剩余消耗成0,那么cnt++,无论如何,将自己消耗后的剩余值传下去。 暴力求解的时间复杂度是O(N^2)。

方法二:使用前缀和+TwoSum的技巧。DFS的过程中,将到达当前结点的前缀和记录进hashmap,由于前缀和可能重复,所以hashmap使用{前缀和 -> 前缀和数量},在进入一个新节点后,先计算该节点的补数有多少个,就知道结束于该点有多少个路径和等于target,然后把当前前缀和数量加一,继续向下递归,最后在DFS退回上一层之前,把当前前缀和的数量在hashmap中减一。 时间复杂度是O(N)。

注意:hashmap一开始要加入哨兵值,也就是,preSum为0的数量默认是1。