4. 分别用递归和非递归方式实现二叉树先序、中序和后序遍历

1、解答：

递归方式很简单，就是调整处理节点和递归左右子节点的顺序。

而非递归方式，就是要利用栈来模拟递归的过程。如果想使用统一的模板来实现三种遍历，中序遍历是一个问题，它的访问顺序和处理顺序是不一致的。解决办法是使用一个空节点来标记访问。即在取得栈中的一个节点非空时，

栈中依次推入该节点和空节点，表示这次是访问，并不处理。如果取栈中的元素为空，就表示这次要弹出栈中的下以哦个非空元素，表示这次是处理这个节点。这样就将三种遍历的不统一的访问和处理顺序统一起来。当然，此时

要注意的是，不能将空节点压栈，否则回导致算法失效。

5. 斐波那契数列问题的递归和动态规划

1、解答：

方法一：

暴力递归--即return f(n - 1) + f(n - 2),这是2的n次方级别的时间复杂度;

方法二：

遍历--从左到右依次计算，直到计算到第n项，这是n级别的空间复杂度;

方法三：

矩阵乘法--F（n）=F（n-1）+F（n-2），是一个二阶递推数列，一定可以用矩阵乘法的形式表示，且状态矩阵为 2×2的矩阵，所以，求斐波那契数列第N项的问题就变成了如何用最快的方法求一个矩阵N次方的问题，这是一个

logn级别的空间复杂度（提示，将N次方转化为位的形式，一个矩阵用于保存累乘的结果，一个矩阵用于计算矩阵的1，2，4，8...次方，也就是记录每一位对应的矩阵乘法结果。

大数据处理问题

1. 公共数据问题

策略：大而化小，分而治之的策略

方法：哈希函数；根据hash值映射到对应小文件；然后依次比较小文件

1、文件A、B各有2T的文件，文件按照行存放了的字符串；找到A、B两个文件中公共的字符串

步骤：

1. 根据内存限制划分文件数目 N；尽量保证每个文件分配的数据是均匀的；
2. 根据哈希值绑定特定文件；遍历A文件；对每一行做hash函数计算；根据哈希值将该行数据映射到一个小文件

【A1-AN中的某一个】；遍历文件B做同样的处理；会得到对应的B1-BN个文件

1. 逐个比较<A1,B1>文件对【不对应的小文件不可能有相同的字符串】；此时数据量足够小，可以装载到

hashmap中进行对比，最后得到结果

拓展：

可能会出现多个文件映射到同一哈希值，如何解决？改变哈希函数；每次遇到冲突映射到小文件则改变哈希函数

2、A,B两个文件各存放50亿url，每个为64Byte，限制内存4G找出公共url