如何给二叉树节点加常数字段实现O(1)复杂度的祖先判断？

Great question! Your initial thought about adding a depth field is a solid start—it lets you immediately rule out cases where x.depth >= y.depth (since an ancestor must be higher up in the tree, hence shallower). But as you noticed, that's not enough on its own. Let's dive into a proven solution that adds just two extra fields per node and lets you answer ancestor queries in O(1) time.

The Euler Tour (In-Time and Out-Time) Approach #

The key here is to assign two integer fields to every node:

• in_time: The timestamp when we first visit the node during a depth-first search (DFS) traversal.
• out_time: The timestamp when we finish visiting all of the node's descendants (i.e., when we backtrack out of the node after processing both left and right children in a binary tree).

How It Works #

When you perform a DFS traversal of the tree:

1. Start with a global counter initialized to 1.
2. When you enter a node, assign in_time = counter and increment the counter.
3. Recursively visit all the node's children (left first, then right for a binary tree).
4. When you finish processing all children and are ready to leave the node, assign out_time = counter - 1 (or increment the counter first, then assign—either way works as long as the relative order is consistent).

Once these fields are set, to check if x is an ancestor of y, you just need to verify three conditions (the third is optional but helpful for quick filtering):

1. x.in_time <= y.in_time (y was visited after x)
2. x.out_time >= y.out_time (y was finished being processed before x)
3. x.depth < y.depth (quick pre-check to eliminate obvious non-ancestors faster)

If all conditions are true, x is definitely an ancestor of y. If any fail, it's not.

Example to Illustrate #

Let's take a simple binary tree:

Root (depth 0)
   /     \
Left (1) Right (1)
   \
   LeftRight (2)

A DFS traversal would assign timestamps like this:

• Root: in_time = 1, out_time = 8
• Left: in_time = 2, out_time = 5
• LeftRight: in_time = 3, out_time = 4
• Right: in_time = 6, out_time = 7

Now, let's test a few cases:

• Is Left an ancestor of LeftRight?
  Left.in_time (2) ≤ LeftRight.in_time (3) → yes; Left.out_time (5) ≥ LeftRight.out_time (4) → yes; Left.depth (1) < LeftRight.depth (2) → yes. So Left is an ancestor.
• Is Root an ancestor of Right?
  Root.in_time (1) ≤ Right.in_time (6) → yes; Root.out_time (8) ≥ Right.out_time (7) → yes; Root.depth (0) < Right.depth (1) → yes. So Root is an ancestor.
• Is Left an ancestor of Right?
  Left.in_time (2) ≤ Right.in_time (6) → yes, but Left.out_time (5) < Right.out_time (7) → no. So Left is not an ancestor.

Why This Works #

The in_time and out_time define an interval that encloses the intervals of all the node's descendants. Any node in the subtree rooted at x will have an in_time between x.in_time and x.out_time, and an out_time within that same range. Non-descendants will either have an in_time before x.in_time, or an out_time after x.out_time.

Benefits #

• Constant extra fields: Only two integers per node—fits your requirement of constant overhead.
• O(1) query time: Just a few comparisons, no tree traversal needed.
• Works for any tree: Not just binary trees—this approach extends to trees with any number of children.

Final Notes #

Your initial depth field pairs perfectly with this approach. Adding it as a quick pre-check lets you skip the in_time/out_time comparisons for cases where x can't possibly be an ancestor (since it's deeper or at the same level), which can speed up queries in practice.

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