二叉树前驱节点和后继节点详解及 Python 代码实现

二叉树的前驱节点和后继节点在二叉树中是非常重要的概念。

前驱节点：在二叉树中，某个节点的前驱节点是指这个节点的左子树中的最右侧节点。如果这个节点没有左子树，那么它的前驱节点就是它的某个祖先节点，这个祖先节点的右子树包含了这个节点。

后继节点：在二叉树中，某个节点的后继节点是指这个节点的右子树中的最左侧节点。如果这个节点没有右子树，那么它的后继节点就是它的某个祖先节点，这个祖先节点的左子树包含了这个节点。

在二叉搜索树中，我们可以利用中序遍历的结果来求出某个节点的前驱节点和后继节点。具体来说，对于某个节点 x：

• 如果 x 有左子树，那么 x 的前驱节点就是其左子树中的最右侧节点，即左子树中最大的节点；
• 如果 x 没有左子树，那么 x 的前驱节点就是它的某个祖先节点，这个祖先节点的右子树包含了 x；
• 如果 x 有右子树，那么 x 的后继节点就是其右子树中的最左侧节点，即右子树中最小的节点；
• 如果 x 没有右子树，那么 x 的后继节点就是它的某个祖先节点，这个祖先节点的左子树包含了 x。

代码示例：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_successor(root: TreeNode, p: TreeNode) -> TreeNode:
    if not root:
        return None

    # 如果 p 有右子树，那么 p 的后继节点就是其右子树中的最左侧节点
    if p.right:
        p = p.right
        while p.left:
            p = p.left
        return p

    # 如果 p 没有右子树，那么 p 的后继节点就是它的某个祖先节点，
    # 这个祖先节点的左子树包含了 p
    succ = None
    while root:
        if p.val < root.val:
            succ = root
            root = root.left
        elif p.val > root.val:
            root = root.right
        else:
            break
    return succ

def inorder_predecessor(root: TreeNode, p: TreeNode) -> TreeNode:
    if not root:
        return None

    # 如果 p 有左子树，那么 p 的前驱节点就是其左子树中的最右侧节点
    if p.left:
        p = p.left
        while p.right:
            p = p.right
        return p

    # 如果 p 没有左子树，那么 p 的前驱节点就是它的某个祖先节点，
    # 这个祖先节点的右子树包含了 p
    pred = None
    while root:
        if p.val < root.val:
            root = root.left
        elif p.val > root.val:
            pred = root
            root = root.right
        else:
            break
    return pred

时间复杂度：O(h)，其中 h 是二叉搜索树的高度。在最坏情况下，二叉搜索树退化成链表，h=n，其中 n 是节点的个数。因此，时间复杂度为 O(n)。

空间复杂度：O(1)。我们只需要常数的空间存储变量。