牛客算法–第九章

题目一
在二叉树中找到一个节点的后继节点
【题目】
现在有一种新的二叉树节点类型如下：
public class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data) {
this.value = data;
}
}
该结构比普通二叉树节点结构多了一个指向父节点的 parent 指针。假设有一棵 Node 类型的节点组
成的二叉树，树中每个节点的 parent 指针都正确地指向自己的父节点，头节点的 parent 指向 null。
只给二叉树中的某个节点 node，请实现返回 node 的后继节点的函数。
后继节点：在二叉树的中序遍历的序列中，node 的下一个节点叫作 node 的后继节点。

总结，两种方法。

第一种方法，题目告知了一个结点的后继结点的序列是中序序列。那么我们可以首先从head开始做中序遍历，然后在中序遍历的序列中找到那个结点，然后那个结点后面的一个结点就是该结点的后继结点。

第二种方法，给了parent指针，假设一个结点距离它后继结点的距离是L,那我们可以只走L的距离就可以。
如果一个结点有右子树，那么他的后继结点就是*这个结点的右子树的最左结点。*
如果一个结点没有右子树，那就从这个结点回溯，一直向上跳，直到找到一个结点是这个结点的父结点的左子树结点，那么这个父结点就是原来结点的后继结点，如下图：

注意：任何一颗树中总会有结点是没有后继结点的。

题目二
遍历二叉树的神级方法
【题目】
给定一棵二叉树的头节点 head，完成二叉树的先序、中序和后序遍历。
【要求】
如果二叉树的节点数为 N，要求时间复杂度为 O(N)，额外空间复杂度为 O(1)。

morris遍历

题目三
找到二叉树中符合搜索二叉树条件的最大拓扑结构
【题目】
给定一棵二叉树的头节点 head，已知所有节点的值都不一样，返回其中最大的、且符合搜索二叉树
条件的拓扑结构的节点数。这里的拓扑结构是指，你可以在二叉树中任意选择某些节点，只要这些节
点是连在一起的，都叫做二叉树的拓扑结构。

有两种方法。
第一种方法，比较简单，但是需要优化。总的思想就是检查一颗树中以每个结点为根结点的情况下成为拓扑结构的可能性。
具体实现就是，假设目前的拓扑结构的根结点是N，则开始依次遍历（可以先序、中序等，随意挑一种）它下面的子结点，每次遍历到新的子结点，就和对应的二叉搜索树序列进行比较，如果在二叉搜索序列中可以找到，说明目前形成的拓扑结构可以成立，否则就不成立。

总结，就是用先序遍历进行扩展，查找可能的新结点，用二叉搜索序列进行检查，检验新结点能否加入拓扑结构之中。

第二种方法用到下面的拓扑共线结构，就是需要每个结点记录，其左右子树分别可以加入到最大拓扑结构中的结点树。

拓扑共线结构

所以第二种方法，用后序遍历的顺序。即“左右根”。

假设我们后序遍历的时候，遍历X的时候，已经得到了L为头的拓扑共线记录和以R为头的拓扑共线记录。而且我们可以根据这些，更新以X为头的拓扑共线记录，那么我们就可以解决这个问题。