thinking3.md

9.找出任意整数的所有路径

  可以通过对二叉树的遍历找出所有的路径，然后判断各条路径上所有结点的值的和是否和给定的整数相等。具体实现方法可以通过对二叉树进行先序遍历来实现，实现思路为：对二叉树进行先序遍历，把遍历的路径记录下来，当遍历到叶子结点时，判断当前路径上所有结点数据的和是否等于给定的整数。

  性能分析：这种方法和二叉树的先序遍历有着相同时间复杂度O(N)，这种方法用一个数组存放遍历路径上结点的值，最坏的情况下空间复杂度为O(N)。

10.对二叉树进行镜像反转

  要实现二叉树的镜像反转，只需交换二叉树中所有结点的左右孩子即可。对所有的结点都做了相同的操作，可以用递归地方法来实现。打印时候用层序打印。

  性能分析：由于对给定的二叉树进行了一次遍历，时间复杂度为O(N)。

11.二叉排序树中找出第一个大于中间值的结点

  首先需要找出二叉排序树中的最大值和最小值。根据二叉排序树的特点，最小值一定是最左下的结点，最大值一定是最右下的结点。接下来对二叉树进行中序遍历，如果当前结点的值小于中间值，那么在这个结点的右子树中接着遍历，否则遍历这个结点的左子树。

  性能分析：这种方法在查找最大结点与最小结点的时间复杂度为O(h)，h为二叉树的高度，对于有N个结点的二叉排序树，最大的高度为O(N)，最小的高度为O(log2N)。

12.找出路径最大的和

  可以通过后序遍历来解决。具体思路如下：

• 求出以root.lchild为起始结点，叶子结点为终结点的最大路径和maxLeft；

• 同理求出以root.rchild为初始结点，叶子结点为终点的最大路径和maxRight。

  包含root结点的最长路径可能包含如下三种情况：

1. leftMax=root.sums+maxLeft(右子树最大路径和可能为负)。
2. rightMax=root.sums+maxRight(左子树最大路径和可能为负)。
3. allMax=root.sums+maxLeft+maxRight(左右子树的最大路径和都不为负)。

  因此，包含root结点的最大路径和为tmpMax=max(leftMax,rightMax,allMax)。在求出包含root结点的最大路径后，如果tmpMax>max，那么更新最大路径和为tmpMax。

  性能分析：二叉树后序遍历的时间复杂度为O(N)，因此，这种方法的时间复杂度也为O(N)。

13.实现反向DNS查找缓存

  要实现反向DNS查找缓存，主要需要完成如下功能：

1. 将IP地址添加到缓存中的URL映射。
2. 根据给定的IP地址查找对应的URL。

  常见的一种解决方案是使用字典法(使用字典来存储IP地址与URL之间的映射关系)。另外一种更好的方法是Trie树。这种方法的主要优点如下：

1. 使用Trie树，在最坏的情况下时间复杂度为O(1)，而哈希方法在平均情况下的时间复杂度为O(1)；
2. Trie树可以实现前缀搜索(对于有相同前缀的IP地址，可以寻找所有的URL)。

  Internet IP地址只包含有11个字母(0到9和.)。所以，本题实现的主要思路为：在Trie树中存储IP地址，而在最后一个结点中存储对应的域名。