問(wèn)題
設(shè)計(jì)一個(gè)算法，找出二叉搜索樹(shù)中指定節(jié)點(diǎn)的“下一個(gè)”節(jié)點(diǎn)（也即中序后繼）抡笼。
如果指定節(jié)點(diǎn)沒(méi)有對(duì)應(yīng)的“下一個(gè)”節(jié)點(diǎn)，則返回null仔戈。
示例 1:
輸入: root = [2,1,3], p = 1
2
/ \
1 3
輸出: 2
示例 2:
輸入: root = [5,3,6,2,4,null,null,1], p = 6
5
/ \
3 6
/ \
2 4
/
1
輸出: null
思路
遞歸
p >= root：中序后繼節(jié)點(diǎn)在右子樹(shù)
p < root：左子樹(shù)不為空就去左子樹(shù)找，否則當(dāng)前節(jié)點(diǎn)就是中序后繼節(jié)點(diǎn)
代碼
Python3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
if not root:
return None
# p >= root，后繼節(jié)點(diǎn)在右子樹(shù)
if root.val <= p.val:
return self.inorderSuccessor(root.right, p)
else:
# 左子樹(shù)不為空
if self.inorderSuccessor(root.left, p):
return self.inorderSuccessor(root.left, p)
# 左子樹(shù)為空监徘，當(dāng)前節(jié)點(diǎn)就是后繼節(jié)點(diǎn)
else:
return root
