牛课堂8.31晚八点开始直播，让左老师伴随你8月最后一天

将搜索二叉树转换成双向链表

【题目】

对二叉树的节点来说，有本身的值域，有指向左孩子和右孩子的两个指针；对双向链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。在结构上，两种结构有相似性，现在有一棵搜索二叉树，请将其转换为一个有序的双向链表。

例如，节点定义为：

public class Node {

public int value;

public Node left;

public Node right;

public Node(int data) {

this.value = data;

}

}

【要求】

所以时间复杂度为O(N)，额外空间复杂度为O(h)，h为二叉树的高度

题目二

一种怪异的节点删除方式

【题目】

链表节点值类型为int型，给定一个链表中的节点node，但不给定整个链表的头节点。如何在链表中删除node？请实现这个函数，并分析这么会出现哪些问题。

【要求】

时间复杂度为O(1)。

题目三

清楚的讲一遍KMP算法以及一个与其相关的推广

【题目】

给定字符串str1和str2，请返回str2在str1中第一次出现的位置；如果str1不包含str2，返回-1

【要求】

时间复杂度O(N)

【推广题目】

给定两棵二叉树的头节点head1和head2，判断head2是不是head1的子树

【要求】

时间复杂度O(N)

题目四

来自观众的一个极好的优化

【题目】

未排序数组中累加和小于或等于给定值的最长子数组长度问题

给定一个无序数组arr，其中元素可正、可负，可0，给定一个整数k。求arr所有的子数组中累加和小于或等于k的最长子数组长度

【例子】

arr=[3,-2,-4,0,6]，k=-2，相加和小于或等于-2的最长子数组为[3,-2,-4,0]，所以结果返回4

【要求】

实现时间复杂度O(N)的方法

【特别说明】

在第二次课上，我们讲过这个题，当时讲解的是时间复杂度O(N*logN)的方法和相关的算法原型。上一周，来自滴滴快车的秦凯杰工程师留言给我，说一个他认识的牛人实现出了时间复杂度O(N)的方法，并把代码发给了我。我仔细阅读之后发现他提供的时间复杂度O(N)的方法是对的。感谢秦凯杰工程师和他的牛人朋友。我们在这次课上详细讲述该方法