在O(1)时间复杂度内判断二叉树中X是否为Y的前驱节点

嘿，这个问题我之前也琢磨过！咱们先把核心需求掰明白：在任意二叉树（不管是不是BST）里，要**O(1)**时间判断节点x是不是节点y的前驱节点，而且允许给节点扩展任意字段。你提到想通过插入时维护前驱字段来实现，思路是对的，只是需要把维护逻辑理清楚，咱们一步步来：

第一步：明确“前驱节点”的定义 #

首先得确认你说的前驱是哪种遍历顺序下的——通常默认是中序遍历的前驱（左子树→根→右子树的顺序里，y的前一个节点），当然如果是前序/后序，逻辑也类似，这里先以中序为例讲解。

第二步：给节点扩展必要的字段 #

给每个树节点添加两个额外的指针字段：

• inorder_prev：指向该节点的中序前驱节点
• inorder_next：指向该节点的中序后继节点

这样一来，判断x是不是y的前驱就超级简单了——直接看 y.inorder_prev == x 就行，这绝对是O(1)时间复杂度，完全符合要求。

第三步：在树的操作中维护这些字段 #

关键在于插入、删除节点时，同步更新相关节点的inorder_prev和inorder_next，不然这些指针就会失效。这里说下核心操作的逻辑：

插入节点z时的维护步骤： #

1. 找到z在中序遍历中的前驱节点p（中序里z的前一个节点），以及后继节点s（中序里z的后一个节点）
2. 设置z的指针：z.inorder_prev = p，z.inorder_next = s
3. 如果p不为空，把p的后继指向z：p.inorder_next = z
4. 如果s不为空，把s的前驱指向z：s.inorder_prev = z

（注：找前驱后继的操作是插入环节的开销，时间复杂度为O(h)，h是树的高度，但这并不影响咱们最终判断操作的O(1)效率）

删除节点z时的维护步骤： #

1. 拿到z的前驱p和后继s
2. 如果p不为空，设置p.inorder_next = s
3. 如果s不为空，设置s.inorder_prev = p
4. 最后释放z的资源即可

额外说明：如果是其他遍历顺序的前驱 #

如果你的需求是前序/后序遍历的前驱，只需要把字段改成preorder_prev/postorder_prev，然后在插入删除时，按照对应遍历顺序找前驱后继来维护指针就行，判断逻辑还是一样的——直接比较y.xxx_prev == x。

这样一套下来，你就能完美实现O(1)时间的判断了，核心就是提前维护好每个节点的前驱指针，用空间换时间，这也是允许扩展节点字段的意义所在～

内容的提问来源于stack exchange，提问作者Dex Sh