难度: Medium
Submission
运行时间: 44 ms
内存: 22.5 MB
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
if not node.right:
curr = node
while curr.parent and curr == curr.parent.right:
curr = curr.parent
return curr.parent
succ = node.right
while succ.left:
succ = succ.left
return succ
Explain
这个题解的思路是根据二叉搜索树的性质来寻找中序后继节点。中序后继节点有两种情况： 1. 如果当前节点有右子树，那么中序后继就是右子树中最左边的节点。 2. 如果当前节点没有右子树，那么中序后继就是当前节点的某个祖先，该祖先的左子树包含当前节点。具体来说，从当前节点向上查找，直到找到一个节点，它是其父节点的左孩子，那么该父节点就是中序后继。
时间复杂度: 平均 O(log(n))，最坏 O(n)
空间复杂度: O(1)
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
if not node.right:
# 情况 2：当前节点没有右子树
curr = node
# 向上查找，直到当前节点是其父节点的左孩子
while curr.parent and curr == curr.parent.right:
curr = curr.parent
# 该父节点就是中序后继
return curr.parent
# 情况 1：当前节点有右子树
succ = node.right
# 在右子树中找最左边的节点
while succ.left:
succ = succ.left
return succ
Explore
在这种情况下，由于节点没有右子树，我们无法通过右子树找到后继节点；同时，因为它没有父节点，也无法通过父节点链向上查找。因此，这种情况下节点是没有中序后继的，函数应返回None。这表示该节点是整个二叉搜索树的最大节点，即中序遍历的最后一个节点。
题解确实考虑到了右子树可能不存在左子节点的情况。如果当前节点的右子树没有左子节点，那么右子树的根节点本身就是中序后继。所以在寻找最左节点的代码中，如果右子树根节点的left属性为None，循环将不会执行，直接返回该右子树根节点为中序后继。
是的，如果一个节点是最右侧的节点且没有中序后继，这意味着在向上查找的过程中，没有找到一个满足条件的节点（即当前节点是其父节点的左孩子），并且最终达到了树的根节点而根节点也没有父节点。在这种情况下，函数将返回None，因为不存在中序后继。这反映了该节点是二叉搜索树中序遍历的最后一个节点。