#牛客堂直播视频#常见面试题精讲（四）（8.12）
【本期题目】
1、如何仅用递归函数和栈操作逆序一个栈
【题目】
一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，而不能用另外的数据结构。
【难度】
尉 ★★☆☆
2、判断一个链表是否为回文结构
【题目】
给定一个链表的头节点head，请判断该链表是不是回文结构。
例如：
1->2->1，返回true。
1->2->2->1，返回true。
15->6->15，返回true。
1->2->3，返回false。
进阶：
如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
3、二叉树的序列化和反序列化
【题目】
二叉树被记录成文件的过程，叫做二叉树的序列化，通过文件内容重建原来二叉树的过程叫做二叉树的反序列化。给定一棵二叉树的头节点head，并已知二叉树节点值的类型为32位整型。请设计一种二叉树序列化和反序列化的方案并用代码实现。
4、构造数组的MaxTree
【题目】
定义二叉树节点如下：
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
一个数组的MaxTree定义如下：
数组必须没有重复元素；
MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点；
包括MaxTree树在内并且在其中的每一颗子树上，值最大的节点都是树的头；
给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，时间复杂度O(N)，额外空间复杂度O(N)
注：下面回帖给出了源代码供参考。
【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者，电子工业出版社7月底将出版发行，书籍涉及算法与数据结构编程题目240道以上，并且个人实现出最优解，大部分题目为面试高频题
【参与牛客堂直播】
每周三晚8:00~9:30，直播页面http://www.nowcoder.com/live/courses
【直播题目讨论】
加入牛客3群260877110
【本期答案领取地址】
加入牛客5群(272820159）
群资料中文件：＃牛客堂直播视频＃2015.8.12答案
投递蔚来等公司10个岗位 >