查找一个二叉树的后继节点

现在有一种特殊的二叉树节点类型，每个节点有个父引用指向他的父节点，根节点的父引用指向null,
找出指定节点的后继节点，后继节点是整个树按照中序遍历时候的下一个节点，整个树的最右节点的后继节点为null，
要求最快获取后继节点，不能采用遍历整个树的方式

public class SuccessorNode {

    static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

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

    //获取后继结点
    static Node getSuccessorNode(Node node) {
        if (node == null)
            return null;
        if (node.right != null) { //右子树不为null, 在右子树上找最左的节点
            Node temp = node.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            return temp;
        }else { // 第二种情况，右子树为null，分两种情况，假如当前节点是他父节点的左孩子，那该父节点就是后继节点，假如当前节点不是他父节点的左孩子，继续往上找，直到父节点是当前节点的左孩子
            Node parent = node.parent;
            while (parent != null && parent.left != node) { //当前节点是整个树的最右节点时，parent最后会等于null,整个树的最右节点是没有后继节点的，直接返回null
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }


    public static void main(String[] args) {

        // 先创建上图的树
        Node head = new Node(1);
        head.left = new Node(2);
        head.left.parent = head;
        head.left.left = new Node(4);
        head.left.left.parent = head.left;
        head.left.right = new Node(5);
        head.left.right.parent = head.left;
        head.left.right.right = new Node(8);
        head.left.right.right.parent = head.left.right;
        head.right = new Node(3);
        head.right.parent = head;
        head.right.left = new Node(6);
        head.right.left.parent = head.right;
        head.right.left.left = new Node(9);
        head.right.left.left.parent = head.right.left;
        head.right.right = new Node(7);
        head.right.right.parent = head.right;

        
        Node node = head; // 测试1
        System.out.println(node.value + "的后继节点 : " + getSuccessorNode(node).value);

        node = head.left.left; // 测试4
        System.out.println(node.value + "的后继节点 : " + getSuccessorNode(node).value);


    }
}