Inorder Successor in BST
Question
Given a binary search tree 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.
Note
If the given node has no in-order successor in the tree, return null.
Challenge
O(h), where h is the height of the BST.
Solution
首先问面试官每个node是否有parent属性。
1) 首先要在bst中找到该节点。
2) 当该节点的右子树为空时,则向上寻找其父节点,父节点中第一个比该节点大的即为其后继节点。如果有parent属性则很好找,但是如果没有parent属性,则我们需要提前记住这个比该节点大的父节点。方法就是,每当root往左移动之前记录下这个root,向右移动则不需要,这样就能记录下与它最近的父节点。(再仔细说一下这个作用:纪录向左移动前的点就是纪录比root点大的下一个点,向右不需要纪录是因为这个点本身比上一个点大,不需要纪录,这个点不可能成为右儿子的successor)。这里还有一个技巧是记录的父节点初始化为null,这样就算要找的节点为最后一个节点(必然一直向右走,所以父节点一直为null),最后也可以返回父节点null。
3) 如果该节点右子树不为空,则其后继节点为右子树上最小值,因此只要找其右子树上最左边的节点即可。
代码如下:
/**
* 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) {
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;
}
}