一、查问后继节点

后继节点：中序遍历时，某个节点的后一个节点即是该节点的后继节点。

规定二叉树的构造如下：

public static class Node {    public int value;    public Node left;    public Node right;    // 父节点    public Node parent;    public Node (int v) {        value = v;    }}

如何疾速的找到某个节点的后继节点

1、思路

1、依照后继节点的定义来查找某个节点的后继节点

即按中序遍历此二叉树，再查找指定节点的后继节点。工夫复杂度是O(N)。显然此办法不是最优解。

2、依据二叉树的构造，以及多的这个parent指针来查找

（1）指定节点X有右树，则X的后继节点就是X右树上最左的孩子。依据后继节点的定义得出的。

（2）X无右树，则依据parent指针往上找，直到找到某个节点是它父节点Y的左孩子为止，则Y就是X的后继节点；如果始终往上都没有找到某个节点是它父节点的左孩子，则该节点是最右的孩子，无后继节点。

Why：因为X是Y左树上的最右孩子，依照中序遍历的程序，遍历完X就是Y了。

工夫复杂度是O(K)（K是指定节点到后继节点的最短节点数）

很显然第二种办法更优。

2、代码

/** * 查找后继节点 *      * @author Java和算法学习：周一 */public static Node successorNode(Node node) {    if (node == null) {        return null;    }    // 有右孩子    if (node.right != null) {        // 找到右树上最左的孩子        return getMaxLeft(node.right);    } else {        // 无右孩子        // 依据parent指针往上找        Node parent = node.parent;        // 没有找到最顶上，且以后节点是父节点的右孩子则始终往上找        while (parent != null && parent.right == node) {            node = parent;            parent = node.parent;        }        // parent蕴含两种状况        // 1）找到最顶上了，即parent是null        // 2）找到某个节点是父节点的左孩子了        return parent;    }}/** * 失去某个节点最左的孩子 */private static Node getMaxLeft(Node right) {    if (right == null) {        return null;    }    while (right.left != null) {        right = right.left;    }    return right;}

二、纸条折痕问题

这是微软已经的一道面试题，这题真的很考查一个人的能力，并不是说它很难，而是考查对算法的一种死记硬背的能力。

1、题目形容

请把一段纸条竖着放在桌子上，而后从纸条的下边向上方对折1次，压出折痕后开展。此时折痕是凹下去的（下折痕），即折痕突起的方向指向纸条的反面。如果从纸条的下边向上方间断对折2次，压出折痕后开展，此时有三条折痕，从上到下顺次是下折痕、下折痕和上折痕。

给定一个输出参数N，代表纸条从下边向上方间断对折N次。请从上到下打印所有折痕的方向。

例如：

N=1时，打印: down（凹）；

N=2时，打印: down（凹）、down（凹）、up（凸）

2、思路

通过屡次对折会发现：下一次的折痕对于上一次而言，总是上凹下凸的。

也就是第二次的折痕，在第一次的凹（1凹）下面是凹（2凹）、上面是凸（2凸）；

第三次的折痕，在2凹的下面是3凹、上面是3凸，在2凸的下面是3凹、上面是3凸；以此类推。

而后顺次开展，放到一个二叉树上，惊奇的发现，从上到下打印所有折痕的方向，就是二叉树的中序遍历。

3、代码

/** * @author Java和算法学习：周一 */public static void paperFolding(int n) {    // 二叉树头节点是凹的    process(1, n, true);}/** * @param i 节点的层数 * @param n 一共多少层 * @param down true=凹，false=凸 */private static void process(int i, int n, boolean down) {    if (i > n) {        return;    }    // 上边是凹    process(i + 1, n, true);    System.out.print(down ? "凹 " : "凸 ");    // 下边是凸    process(i + 1, n, false);}

是不是发现，思路对了一下就恍然大悟了，死记硬背也是一种能力。

本文代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/SuccessorNode.java