[Leetcode] Inorder Successor in BST 二叉搜索树中序遍历找后继

2016-06-26 10:17:00

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的后继，两种情况：

p有右孩子：后继为右孩子的最左孩子
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.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) //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) {
suc = root;
root = root.left;
}
}
return suc;
}
}
public TreeNode findLeftMost(TreeNode root) {
while (root.left != null) {
root = root.left;
}
return root;
}
}