1. /**
    2.  * 面试题8：二叉树的下一个节点
    3.  * 给定一颗二叉树和其中的一个节点，如何找出中序遍历的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针
    4.  */
    5. public class No8 {
    6.     public static void main(String[] args) {
    7.         int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
    8.         int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
    9.         //使用面试题7重建二叉树来构建测试用例
    10.         BinaryTree root = No7.reConstructBinaryTree(pre, in);
    11.         BinaryTree.printInTree(root);
    12.         BinaryTree result = No8.nextNode(root);
    13.         System.out.println(result.value);
    14.     }
    16.     public static BinaryTree nextNode(BinaryTree currentNode) {
    17.         if (currentNode == null) {
    18.             return null;
    19.         }
    20.         BinaryTree result;
    21.         if (currentNode.right != null) {
    22.             result = currentNode.right;
    23.             while (result.left != null) {
    24.                 result = result.left;
    25.             }
    26.             return result;
    27.         }
    29.         if (currentNode == currentNode.pre.left) {
    30.             return currentNode.pre;
    31.         } else {
    32.             result = currentNode.pre;
    33.             while (result != null) {
    34.                 if (result == result.pre.left) {
    35.                     return result;
    36.                 } else {
    37.                     result = result.pre;
    38.                 }
    39.             }
    40.             return null;
    41.         }
    42.     }
    43. }

    寻找二叉树的中序遍历的下一个节点流程图如下：

    总结（TODO）：
    寻找二叉树的前序遍历的下一个节点流程图：
    寻找二叉树的后序遍历的下一个节点流程图：