Find Next Higher Key in BST (Given Parent)

找后继节点, 但是这里给了父节点. 很简单的考虑一下几种情况:
引用一下http://www.algoqueue.com/的图

比如3, 有右节点, 所以我们返回右节点的最左节点(后继)..

比如2, 没有右节点, 但是2是父节点3的左节点, 所以返回3.

假设没有7, 6没有右节点(没有7), 但是6是3(父节点)的右节点,所以我们只能往上找, 直到找到3是8的左节点, 返回8.

package Learning;/**

import java.util.*;

public class NextHigherKeyinBST {
    static class TreeNode {     // Node 有 parent
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        int val;
        private TreeNode(){}
        public TreeNode(TreeNode p, int val) {
            this.parent = p;
            this.val = val;
        }
        public TreeNode parent(){return parent;}
        public TreeNode left() {return left;}
        public TreeNode right() {return  right;}
    }
    public static TreeNode findNextHigherNodeInBST(TreeNode node){

     /* 如果root是null, 就返回 null*/
        if (node == null)
            return null;

     /* 如果有右子节点, 返回后继节点, 就是右边子节点的最左子节点*/
        if (node.right() != null)
            return findLeftMostNode(node.right());

     /* 如果没有右节点,找到最上边的父节点,直到当前节点不是父节点的右节点(这里反向思维, 有两种情况, 一个是当前节点是父节点的左节点, 因为是BST,
     所以这种情况下, 应该直接返回父节点. 第二种是当前节点是父节点的右节点, 这种情况下, 父节点比当前节点小, 所以要一直往上找, 直到当前节点是父节点的
     左节点)*/
        TreeNode parent = node.parent();
        while (parent != null  &&  node == parent.right()){
            node = parent;
            parent = parent.parent();
        }

        return parent;
    }

    public static TreeNode findLeftMostNode(TreeNode node){
        if(node == null)
            return null;
        while(node.left != null)
            node = node.left;
        return node;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(null, 8);
        root.left = new TreeNode(root,3);
        root.right = new TreeNode(root,10);
        root.left.left = new TreeNode(root.left,2);
        root.left.right = new TreeNode(root.left,6);
        root.left.left.left = new TreeNode(root.left.left,1);
        root.left.right = new TreeNode(root.left,6);
        root.left.right.left = new TreeNode(root.left.right,4);
        root.right.right = new TreeNode(root.right,14);
        root.right.right.left = new TreeNode(root.right.right,13);

        System.out.println(findNextHigherNodeInBST(root.left.right).val);
    }
}