二叉搜索树中的中序后继

Submission

运行时间: 40 ms

内存: 19.5 MB

# 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) -> Optional[TreeNode]:
        if not p:
            return None
        if p.right:
            q = p.right
            while q.left:
                q = q.left
            return q
        if p.val == root.val:
            return None
        nodeStay = root
        nodeIter = root
        while nodeIter.val != p.val:
            if nodeIter.val < p.val:
                nodeIter = nodeIter.right
            else:
                nodeStay = nodeIter
                nodeIter = nodeIter.left
        # print(nodeStay.val, nodeIter.val, p.val)
        if nodeStay.val < p.val :
            return None
        else:
            return nodeStay

Explain

该题解的思路是利用二叉搜索树的性质，中序遍历的后继节点有以下两种情况： 1. 如果给定节点 p 有右子树，则其中序后继为右子树中的最左节点。 2. 如果给定节点 p 没有右子树，则从根节点开始遍历，记录最后一个值小于 p 的节点，即为 p 的中序后继。

时间复杂度: O(h)，其中 h 为二叉搜索树的高度，平均情况下为 O(log(n))

空间复杂度: O(1)

```python
# 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) -> Optional[TreeNode]:
        if not p:
            return None
        
        # 如果给定节点 p 有右子树，则其中序后继为右子树中的最左节点
        if p.right:
            q = p.right
            while q.left:
                q = q.left
            return q
        
        # 如果 p 是根节点，且没有右子树，则没有中序后继
        if p.val == root.val:
            return None
        
        nodeStay = root  # 记录最后一个值小于 p 的节点
        nodeIter = root  # 用于遍历二叉搜索树的指针
        
        # 从根节点开始遍历，找到给定节点 p
        while nodeIter.val != p.val:
            if nodeIter.val < p.val:
                nodeIter = nodeIter.right
            else:
                nodeStay = nodeIter
                nodeIter = nodeIter.left
        
        # 如果 p 的值大于 nodeStay，说明 p 没有中序后继
        if nodeStay.val < p.val:
            return None
        else:
            return nodeStay
```

Explore

这一结论基于二叉搜索树的中序遍历特性。在二叉搜索树中，中序遍历会按照节点值的升序进行。若节点 p 有右子树，按照中序遍历的规则，p 的后继节点是其右子树中最小的节点，即右子树中最左侧的节点。这是因为在中序遍历中，任何节点的右子树中的遍历开始于该右子树的最左侧节点。

这种选择是基于中序遍历的顺序和二叉搜索树的属性。在中序遍历中，如果节点 p 没有右子树，那么其后继节点是在遍历序列中首次出现大于 p 的节点的父节点，这个父节点的值必须是所有大于 p 值的节点中最小的，即最后一个在遍历到 p 之前被访问的节点。这是因为在向上回溯过程中，这是第一个因为左子树遍历完成而被访问的节点。

题解的处理方式在遇到值等于 p 的节点的情况下可能存在问题。如果二叉树中有多个节点的值等于 p，并且这些节点构成了一个子树，那么仅仅记录最后一个值小于 p 的节点可能不足以确定正确的后继。在这种情况下，正确的后继应该是等于 p 值的节点的子树中的最左节点，或者是这些节点的父节点的后继，取决于具体的树结构。

这种处理不完全正确。根节点没有右子树不一定意味着它就没有中序后继。如果根节点是整棵树的最大值，确实没有中序后继；但如果根节点参与了更大的树结构，例如作为另一个树节点的左子树，那么根节点的后继应该是其父节点。因此，题解的这部分代码应该考虑根节点在整个树结构中的位置，而不应该仅仅因为它是根节点就断定没有后继。