这个题直接in-order是O(n)。。要求应该是lgn之类的。
分情况讨论：
有右节点，go right，然后无限往左到，直到左边是NULL，就停止，停止的地方就是答案。
没有右节点，就要traverse了。规则是，找到第一个大于P的点，找不到就是NULL，找到就保存下来。
当前点大于P，保存当前点，然后走左边；
小于P，走右边；
等于P停止，返还保存的点。
public class Solution
{
TreeNode prev = null;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p)
{
if(root == null) return null;
if(p.right != null)
{
TreeNode temp = p.right;
while(temp.left != null) temp = temp.left;
return temp;
}
else helper(root,p.val);
return prev;
}
public void helper(TreeNode root, int val)
{
if(root.val == val) return;
if(root.val < val) helper(root.right,val);
else
{
prev = root;
helper(root.left,val);
}
}
}
貌似可以不判断有没有右节点，上来就直接干也OK。二刷再说。。
二刷。
对于BST来说，in-order就是从小到大排列，找next child，就是大于P中最小的数。
从ROOT开始利用BST的大小特性往P逼近，如果当前NODE的值大于P，就记录下来，并且缩小当前值（go left)；如果小于P，说明P可能在parent的右支，或者当前的右支的某一个左支：
前者返还记录的Parent，因为往右遍历的所有值都小于P，不会再找到一个大于P的值并记录；
后者会在右支的某一个点大于P，记录那个点，以那个点为ROOT，往左找，就又回到了一开始的大小判断。
。。说的很乱，但是思路很简单。
O(lgn)，或者O(height)跟高度有关。
也可以直接遍历。。就O(n) time, O(n) space
public class Solution {
TreeNode parent = null;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null || p == null) return null;
TreeNode res = null;
TreeNode temp = root;
while (temp != null) {
if (temp.val > p.val) {
res = temp;
temp = temp.left;
} else {
temp = temp.right;
}
}
return res;
}
}