[Locked] Inorder Successor in BST

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.

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.

分析:

  一般情况下,目标节点的右子节点即为中序下一个节点;如果该目标节点无右子节点,则中序下一个节点为从根节点到搜索目标节点过程中最后一次做出左节点遍历的节点。

代码:

TreeNode *successor(TreeNode *root, TreeNode *p) {
TreeNode *cur = root, *record = NULL;
while(cur != p) {
if(p->val < cur->val) {
record = cur;
cur = cur->left;
}
else
cur = cur->right;
}
return cur->right ? cur->right : record;
}
上一篇:利用Spring.Net技术打造可切换的分布式缓存读写类


下一篇:《Genesis-3D开源游戏引擎完整实例教程-2D射击游戏篇05:角色中弹》