Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

栈法

复杂度

O(H) 时间 O(H) 空间

思路

这道题给了BST和p，找p的后继，两种情况：

1. p有右孩子：后继为右孩子的最左孩子

2. p无右孩子：后继为离它最近的第一个大于他的爹，他的爹中如果没有大于它的，返回Null

情况1比较简单，情况2用栈记录下他的爹们

注意

一开始当成了二叉树找后继，可是节点没有parent指针，一般这种题会有一个方便找爹的线索，不然就是纯搜索问题了。果然仔细看了题是二叉搜索树，这样就可以更方便的找爹了。如果不是二叉搜索树，只是一个二叉树的话，其实也并不难，跟上面的情况分析基本不变，只是当p没有有右孩子的时候，要一直找找到一个爹使得当前节点作为它的左孩子，这个爹就是要找的后继。

代码

public class Solution {    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {        if (p.right != null) {            return findLeftMost(p.right);        }        else {            Stack
    
      stk = new Stack
     
      ();            while (root != p) {                stk.push(root);                if (root.val < p.val)                    root = root.right;                else if (root.val > p.val)                    root = root.left;            }            if (stk.isEmpty())  //root == p, no successor                return null;            //as long as we get here, stack has at least one element            TreeNode parent = stk.pop();    //let parent be the nearest parent            while (!stk.isEmpty() && parent.val <= p.val) {                 parent = stk.pop();            }            if (parent.val > p.val) //finally find one bigger than p.val                return parent;            return null;    //no one bigger than p.val, it must be stack is empty                    }    }    public TreeNode findLeftMost(TreeNode root) {        while (root.left != null) {            root = root.left;        }        return root;    }}
     
    

BST查找标记法

复杂度

O(H) 时间 O(H) 空间

思路

其实并不需要用栈，情况1不变，情况2中，后继只可能是比P的value大的P的爹，当我们从根到p的时候其实肯定会路过访问这个爹，所以我们用个变量在从根找p的过程中标记所有比p的value大的节点，离p最近的那个就是要找的答案。

注意

请看代码

代码

public class Solution {    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {        if (p.right != null) {            return findLeftMost(p.right);        }        else {            TreeNode suc = null;            while (root != p) {                if (root.val < p.val)                    root = root.right;                else if (root.val > p.val) {                    suc = root;                    root = root.left;                }            }            return suc;        }    }    public TreeNode findLeftMost(TreeNode root) {        while (root.left != null) {            root = root.left;        }        return root;    }}