python3 模拟 二叉树的中序遍历

这题如果要把数组构造出来的话数组长度可能过大(2^n-1)，所以不可以直接构造数组，而是要模拟这个数组
首先先观察一下这个数组：

p(1) = [1]
p(2) = [1, 2, 1]
p(3) = [1, 2, 1, 3, 1, 2, 1]
p(4) = [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]

可以看到这很像一个满二叉树，那我们可以试着采用中序遍历
树的结构可视为：[p(i-1)]+i+[p(i-1)]
代码：

#类似中序遍历了一个满二叉树
def find(n,k):
    def gl(i):
        return (1<<i)-1#相当于2^i-1：构造p（i）时的数组长度
    def dfs(i,k):
        if i==1:#最底层是1
            return 1#遍历到了最底层
        l=gl(i-1)
        if k<=l:#树的左边
            return dfs(i-1,k)
        elif k==l+1:#中间
            return i
        else :#树的右边
            return dfs(i-1,k-l-1)
    return dfs(n,k)

x=input().split()
n=int(x[0])
k=int(x[1])
print(find(n,k))