# 285. Inorder Successor in BST

## 刷题内容

• https://leetcode.com/problems/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.

Example 1:

Input: root = [2,1,3], p = 1

2
/ \
1   3

Output: 2
Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6

5
/ \
3   6
/ \
2   4
/
1

Output: null


## 解题方案

BST的特性，对于一个node，它的所有左侧node都比它小，它的所有右侧node都比它大。最小的元素在最左边，最大的元素在最右边。

        3
/
1
/  \
0    2


function Succ(x)
if Right(x) ̸= NIL then
return Min(Right(x))
else
p ← Parent(x)
while p ̸= NIL and x = Right(p) do
x←p
p ← Parent(p)
return p


class Solution(object):
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
def minNode(node):
while node.left:
node = node.left
return node

def searchP(root, p):
if not root or root.val == p.val:
return None
else:
succ = None
while root != None and p.val != root.val:
if p.val < root.val:
succ = root
root = root.left
else:
root = root.right
return succ

if p.right:
return minNode(p.right)
else:
return searchP(root, p)


apachecn/AiLearning