题目描述：

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

分析：

根据中序遍历的特点，要找到下一个节点有三种情况：
1.当前节点包含右节点，则需要找到右节点的左节点，没有左节点，返回当前节点
2.当前节点不包含右节点，分两种情况考虑：
1）当前节点为父节点的左节点，返回父节点
2）当前节点为父节点的右节点，则把其父节点作为下一个遍历的节点，向上回溯，直到找到节点没有父节点或者节点是其父节点的左孩子为止。

image.png

public class FindNextNode {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);

        TreeNode node11 = new TreeNode(4);
        TreeNode node12 = new TreeNode(5);

        TreeNode node21 = new TreeNode(6);
        TreeNode node22 = new TreeNode(7);

        TreeNode node112 = new TreeNode(8);

        root.left = node1;
        root.right = node2;
        root.parent = null;

        node1.left = node11;
        node1.right = node12;
        node1.parent = root;

        node2.left = node21;
        node2.right = node22;
        node2.parent = null;

        node11.right = node112;
        node11.parent = node1;

        node12.parent = node1;

        node21.parent = node2;
        node22.parent = node2;

        System.out.println(findNextNode(node21)); //输入：6 输出：3
        System.out.println(findNextNode(node12)); //输入：5  输出：1
        System.out.println(findNextNode(node1)); //输入：2   输出：5
        System.out.println(findNextNode(root)); //输入：1   输出：6

    }

    public static TreeNode findNextNode(TreeNode node) {
        if (node == null) return node;
        //1.包含右子树
        if (node.right != null) {
            TreeNode rightNode = node.right;
            while (rightNode.left != null) {
                rightNode = rightNode.left;
            }
            System.out.println(rightNode.value);
            return rightNode;
        }

        if (node.parent == null) {
            System.out.println("null");
            return null;
        }

        //父节点的左子树
        if (node.parent.left == node) {
            System.out.println(node.parent.value);
            return node.parent;
        }

        //父节点的右子树
        TreeNode temp = node.parent;
        while (temp.parent != null) {
            if (temp.parent.left == temp) {
                System.out.println(temp.parent.value);
                return temp.parent;
            }
            temp = temp.parent;
        }

        return null;
    }

    static class TreeNode {
        int value;
        TreeNode parent;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}