LeetCode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k. 思路 基本思路是,假设当前运行到nums[i]的位置,则需要往前看k个数,并且找到其中任意一个数x满足 nums[i]-t <= x <=nums[i]+t。可以利用一个大小为k的二叉搜索树解决搜索范围的问题(问题就转变为:找到第一个>=nums[i]-t的数,判断他是否<=nums[i]+t)。整个算法的时间复杂度是O(N * logk),N为数组长度。 下面代码中用set实现,set是用红黑树实现的。 代码

 

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

思路 title真是长..给前序遍历和中序遍历,构造二叉树。 前序遍历就是Node, Left, Right,而中序遍历是Left, Node, Right,因此给一个前序遍历的序列,他的第一个节点肯定就是那个Node,然后在中序序列里找,就能把序列分成左中右三部分。 自然地就要用递归啦~ 代码

 

LeetCode 103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

思路 记住上一行的输出(结果)节点,每一次从后往前读出下一行,这样第2,4,6次读的时候其实就会翻转成正向了。唯一的问题是左右子节点写入下一行的顺序,按照当前顺序区分一下就行。不是左右左右,就是右左右左,具体看code吧。 代码

 

LeetCode 173. Binary Search Tree Iterator

思路 画一个简单的BST,然后可以看出有三种情况 如果当前节点有右孩子,那就在右子树里找到值最小的那个,显然是右子树里最左下侧的那个节点 如果当前节点没有右孩子,由于左子树的值肯定都比当前节点的值小,左右要找父节点 如果找到某个父节点的值比当前节点值大,那这个父节点就是下一节点 否则,当前节点就是最后一个节点 因此,需要一个栈结构记录当前节点的父亲们(有点像调用栈)。 测试例:NULL根节点,只有一个节点,只有单侧树 代码

 

LeetCode 102. Binary Tree Level Order Traversal

练手水题,直接贴代码。快转正面试了,虚啊,鬼晓得BOSS会问点什么。

 

LeetCode 116. Populating Next Right Pointers in Each Node

思路 发现是一个树的遍历的题目,而且题目限制的比较死,是个满二叉树,这样处理的时候就避免了比较烦人的跨树指针的情况。比如下面这种建立4->5的指针:

第一时间想到的解法是弄个工作队列,然后一层一层遍历下去就行了,这个解法的空间复杂度是O(n),不符合题目要求。后来再一想,其实既然上一层已经把下一层的next指针建立好了,就不用再从工作队列里去“回忆”了,只要在每一行的开头记住下一行在哪里就行,这样只要O(1)空间复杂度。 另外是如何设置next指针,一共有两个情况: node自己的左孩子和右孩子连起来 node的右孩子与node右侧节点它的左孩子连起来 代码 O(n)空间复杂度方法

O(1)空间复杂度方法

 

LeetCode 331. Verify Preorder Serialization of a Binary Tree

如家网络实在太卡了,不过还好没有人劫@!$#@W… 稍微说一下思路把,这个问题就是判断某一层上的节点它的孩子会不会“溢出”,或者第一层的节点有没有完全闭合。我用一个栈来保存每一层的孩子数目(包括null): 当碰到数字的时候,压一层计数为0的栈,表示新开了一层并且这一层的孩子数为0 当碰到#号时,说明多了一个空孩子,当前栈顶的计数+1,并且判断当前栈顶的计数是否>=2了,如果是的话,那说明这一层已经满了,那就退栈,然后再继续给新栈顶计数+1,继续判断是否满….如此往复 由于有了#表示空节点所以层级变得明确,举个例子:一个叶节点读入两个#,当前层的计数等于2后就退栈,并且给父亲层的计数器+1(表示下一层已经结束了,父亲多了一个左/右孩子)。 代码(好久没有纯手打一遍AC了)

BTW,苏州的交通状况和路面比杭州好多了。