二叉树前驱节点：查找算法及 Python 代码实现

二叉树中，一个节点的前驱节点是指，在中序遍历中，该节点的前一个节点。如果一个节点有左子树，那么它的前驱节点就是它的左子树中最右边的节点。如果没有左子树，那么它的前驱节点就是它的祖先中第一个有右子树的节点。

代码实现：

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

def find_predecessor(root: TreeNode, node: TreeNode) -> TreeNode:
    if not root or not node:
        return None

    # 如果该节点有左子树，则前驱节点为左子树中最右边的节点
    if node.left:
        p = node.left
        while p.right:
            p = p.right
        return p

    # 如果该节点没有左子树，则前驱节点为第一个有右子树的祖先节点
    p = root
    pre = None
    while p != node:
        if p.val > node.val:
            p = p.left
        else:
            pre = p
            p = p.right
    return pre

时间复杂度为 $O(h)$，其中 $h$ 为树的高度。