无需遍历至根节点的二叉树两节点深度差计算问题咨询

核心逻辑利用双指针同步向上遍历，仅需单个节点遍历至根即可得到深度差，满足无额外内存、无需双节点遍历至根的限制，时间复杂度为O(min(d_p, d_q))，d_p、d_q分别为p、q节点的深度，在LCA距离根较远的场景下，相较于常规双节点全遍历到根的方案效率提升显著。

具体实现步骤 #

• 初始化两个遍历指针 cur_p = p、cur_q = q，初始化深度差变量 delta = 0
• 循环执行遍历操作，只要cur_p和cur_q都存在父节点（未走到根）：
  • cur_p向上移动到父节点
  • cur_q向上移动到父节点
• 循环结束后，判断哪个指针先走到根：
  • 如果cur_p没有父节点（p先走到根）：说明p比q浅，继续移动cur_q直到其走到根，每移动一次delta -= 1
  • 如果cur_q没有父节点（q先走到根）：说明q比p浅，继续移动cur_p直到其走到根，每移动一次delta += 1
• 最终返回的delta就是p和q的深度差，正值代表p更深，负值代表q更深，0代表二者深度相同

伪代码示例 #

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

def get_depth_diff(root, p, q):
    cur_p, cur_q = p, q
    delta = 0
    # 同步向上走，直到其中一个到根
    while cur_p.parent and cur_q.parent:
        cur_p = cur_p.parent
        cur_q = cur_q.parent
    # 处理剩余步数
    if not cur_p.parent:
        # p先到根，q更深
        while cur_q.parent:
            cur_q = cur_q.parent
            delta -= 1
    else:
        # q先到根，p更深
        while cur_p.parent:
            cur_p = cur_p.parent
            delta += 1
    return delta

方案符合题目所有限制：

1. 仅使用3个普通变量，无数组、哈希表等额外存储结构，空间复杂度O(1)
2. 仅需深度更浅的节点遍历至根，另一个节点无需走到根，完全满足“无需将两个节点都向上遍历至根节点”的要求
3. 当LCA距离根较远时，两个节点深度差通常较小，后续遍历剩余步数的开销可以忽略，整体效率很高

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