CC150-Tree and Graph

General

平衡树用到O(log N)次递归调用。

图考虑： 遍历节点 / 遍历边

拓扑排序 / 特殊的树变成图来解决

4.4 给定一棵二叉树，设计一个算法，创建含有某一深度上所有结点的链表（比如，若一 棵树的深度为D，则会创建出D个链表）。

解法:

任意方式 遍历整棵树,记住结点位于哪一层即可

4.6 设计一个算法，找出二叉查找树中指定结点的“下一个”结点（也即中序后继）。可 以假定每个结点都含有指向父结点的连接。（第 54 页）

认真想

4.8 你有两棵非常大的二叉树：T1，有几百万个结点；T2，有几百个结点。设计一个算 法，判断T2 是否为T1 的子树。 如果T1 有这么一个结点n，其子树与T2 一模一样，则T2 为T1 的子树。也就是说，从结点n 处把树砍断，得到的树与T2 完全相同。（第 54 页）

在规模较小且较简单的问题中， 我们可以创建一个字符串， 表示中序和前序遍历。 
若T2 前序遍历是T1前序遍历的子串，并且T2中序遍历是T1中序遍历的子串，则T2为T1的子树。
利用后缀树可以在线性时间内检查是否为子串，因此就最差情况的时间复杂度而言，
注意，我们需要在字符串中插入特殊字符，表示左结点或右结点为NULL的情况。否则，我们就无法区分以下特殊情况

另一种解法是搜遍较大的那棵树T1。 每当T1的某个结点与T2的根结点匹配时， 就调用 treeMatch。
treeMatch方法会比较两棵子树，检查两者是否相同。

4.9 给定一棵二叉树，其中每个结点都含有一个数值。设计一个算法，打印结点数值总和 等于某个给定值的所有路径。注意，路径不一定非得从二叉树的根结点或叶结点开始或结束。（第 54 页）