Very interesting problem!
http://www.lintcode.com/zh-cn/problem/inorder-successor-in-binary-search-tree/
Description:
Given a binary search tree (See Definition) and a node in it, find the in-order successor of that node in the BST.
Example:
Given tree = [2,1] and node = 1:
2
/
1
return node 2.
Given tree = [2,1,3] and node = 2:
2
/ 1 3
return node 3.
Challenge:
O(h), where h is the height of the BST.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { // write your code here TreeNode successor = null; while (root != null && root.val != p.val) { if (root.val > p.val) { successor = root; root = root.left; } else { root = root.right; } } if (root == null) { return null; } if (root.right == null) { return successor; } root = root.right; while (root.left != null) { root = root.left; } return root; } }
三种情况：
1，p有右儿子，这个时候就找右儿子一直找左儿子，直到null，可以根据in order的算法来想
2，p没有右儿子，这个时候就要找p的祖先，这个时候存在两种情况，如果p对p的祖先而言都是右儿子，这个时候就没有in order successor了，因为p就是in order的最后一个元素，如果不是这样，那么就找最近的对p而言是p是左儿子的，所以在这个程序中初始化successor为null，然后只在root.val > p.val时才更新successor,这两点很重要！
LintCode : Inorder Successor in Binary Search Tree
原文：http://www.cnblogs.com/dingjunnan/p/5399978.html
