Google Foobar Ion Flux Relabeling问题代码bug排查求助

Lambda指挥官优化离子通量转换器树的实验失败，部分转换器的位置标签损坏。需要重建的是完美二叉树，节点编号按后序遍历从1开始标注。例如高度为3的树结构如下：

7
    /   \
  3      6
 /  \   / \
1   2  4   5

任务要求 #

编写函数answer(h, q)：

• h：完美二叉树的高度，取值范围1 <= h <= 30，h=1表示仅含根节点的树，h=2表示根节点+两个叶子节点，以此类推
• q：正整数列表，每个元素是某个转换器的编号，范围1到2^h-1，列表长度1~10000
• 返回列表p：每个元素对应q中节点的父节点编号，根节点的父节点为-1

示例：answer(3, [1, 4, 7])返回[3, 6, -1]

我的解决方案 #

#root: root
#result: list that tracks the history of the nodes along the path
#parent: list of the parent node(s)
#subt: what ill be subtracting from the node if I go left
#cnode: current node
#part: partition that separates whether the node goes left or right on the tree
#_r: resets the values at the beginning of each cycle 


def solution(h, q):
    root = 1
    result = []
    parent = []
    
    # This give the root Value of the Binary tree
    for i in range(1,h):
        root = (root*2)+1
        subt = root
    
    subt = (subt + 1)/2
    cnode = root
    part = ((cnode - 1)/2)+1
    
    cnode_r = cnode
    part_r = part
    subt_r = subt
    
    result.append(cnode)
    
    for x in q:
        cnode = cnode_r
        part = part_r 
        subt = subt_r
        flag = True
        if x == root:
            parent.append(-1)
        else:
            while flag:
                if x == cnode:
                    flag = False
                elif x < part:
                    cnode = cnode - subt
                    subt = subt/2
                    part = (cnode - subt) + 1
                    result.append(cnode)
                elif x >= part:
                    cnode = cnode-1
                    subt = subt/2
                    part = (cnode - subt) + 1
                    result.append(cnode)
            if x == cnode:
                parent.append(result[-2])
    parent = [int(x) for x in parent]
    return parent

问题现状 #

代码通过了公开测试用例，但无法通过隐藏测试，手动排查多天找不到根本性错误。

测试用例 #

测试用例1 #

输入：

(int) h = 3
(int list) q = [7, 3, 5, 1]

输出：

(int list) [-1, 7, 6, 3]

测试用例2 #

输入：

(int) h = 5
(int list) q = [19, 14, 28]

输出：

(int list) [21, 15, 29]

求帮助排查代码中的错误或提供排查方向。

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