Given a binary search tree (See Definition) and a node in it, find the in-order successor of that node in the BST.
If the given node has no in-order successor in the tree, returnnull.
Example
Given tree =[2,1]and node =1:
2
/
1
return node2.
Given tree =[2,1,3]and node =2:
2
/ \
1 3
return node3.
Challenge
O(h), where h is the height of the BST.
Notice
It's guaranteed_p_is one node in the given tree. (You can directly compare the memory address to find p)
分析
就是中序遍历加条件
"""
Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
class Solution:
"""
@param: root: The root of the BST.
@param: p: You need find the successor node of p.
@return: Successor of p.
"""
def inorderSuccessor(self, root, p):
# write your code here
stack = []
cur = root
prev = None
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if prev and prev.val == p.val:
return cur
prev = cur
cur = cur.right
return None
递归
这里相当于二分，找到第一个root.val>p.val
"""
Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
class Solution:
"""
@param: root: The root of the BST.
@param: p: You need find the successor node of p.
@return: Successor of p.
"""
def inorderSuccessor(self, root, p):
# write your code here
if not root or not p:
return None
if root.val<=p.val:
return self.inorderSuccessor(root.right,p)
else:
left = self.inorderSuccessor(root.left,p)
return left if left else root