如何获取超大型二元组二叉树的节点层级并优化现有低效代码

云原生阿岚

2026-9-23

问题分析

你当前的实现采用暴力枚举所有路径的方案，时间复杂度为O(2^max(x,y))，当节点层级超过20之后，运算量会指数级暴涨，完全无法处理高节点查询场景。
核心问题在于你选择了从根节点正向穷举所有可能路径的思路，忽略了该二叉树的节点特性：每个非根节点的父节点是唯一的，不需要穷举。

优化思路

采用反向推导法，从目标节点向根节点(1,1)回溯：

任意非根节点(a,b)的父节点唯一：
- 如果a > b：说明该节点是父节点的左子节点，父节点为(a-b, b)
- 如果b > a：说明该节点是父节点的右子节点，父节点为(a, b-a)
- 如果a == b：仅当a=b=1时为根节点，其余情况节点不存在
回溯过程中累计步数，直到到达根节点(1,1)，累计步数就是目标层级
可进一步优化连续减法场景：当其中一个数远大于另一个时，直接用除法计算可连续回溯的步数，进一步把复杂度降到O(log(max(x,y)))

优化后代码

def solution(x, y):
    a = int(x)
    b = int(y)
    level = 0
    while a > 0 and b > 0:
        if a == 1 and b == 1:
            return level
        if a > b:
            # 优化连续左节点回溯场景
            if b == 1:
                level += a - 1
                return level
            cnt = a // b
            level += cnt
            a = a % b
        else:
            # 优化连续右节点回溯场景
            if a == 1:
                level += b - 1
                return level
            cnt = b // a
            level += cnt
            b = b % a
    return 'impossible'

效果验证