G家店面 - 已拒

my two cents:

1. mem = {}
   
2. def find_parent(n, target):
   
3.     if target >= (1<<n)-1:
   
4.         return -1
   
5.    
   
6.     if target in mem:
   
7.         return mem[target]
   
8.    
   
9.     if (target+1)&target==0:
   
10.         mem[target] = target*2+1
    
11.         return mem[target]
    
12.    
    
13.     if (target+2)&(target+1)==0:
    
14.         mem[target] = target+1
    
15.         return mem[target]
    
16.    
    
17.     i = n-1
    
18.     while i>=0:
    
19.         tmp = 1<<i
    
20.         if target & tmp !=0:
    
21.             mem[target] = find_parent(n,target - tmp + 1) + tmp - 1
    
22.             return mem[target]
    
23.         i -= 1

复制代码

谢谢分享！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

qqaas 发表于 2019-5-8 06:03
办法一 开哈希表 便利一次树的同时 存子节点值：父节点值到哈希表里
办法二 修改树的结构，加一个TreeNode  ...

开哈希和修改树结构 都是一个概念 有一个从curNode->parent的映射

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

louzhu 最后是啥思路啊

lq24 发表于 2019-5-8 08:54
假如n=3, 把所有数x都做一个 x=2^n -1 -x; 的变换，变换以后，x 的parent 就是 (x-1)/2 了，算出来以后，再 ...

层主能给个例子么？n = 3就行 多谢多谢 最后是怎么得到所有的parent节点的？

For finding the parent of one node in the tree. The recursive calls can be improved (vastly) by memorization but I think this shows the basic idea.

1. int findParent(int n, int x) {
   
2.     if(x < 3) return 3;
   
3.         if(x == (1 >> n) - 1) return -1; // root
   
4. 
   
5.     // If x is the left or right child of the root
   
6.     if(x == (1 >> (n - 1)) || x == (1 >> n) - 2)
   
7.         return (1 >> n) - 1;
   
8. 
   
9.     if(x < (1 >> (n - 1))) // In left subtree
   
10.         return findParent(n - 1, x);
    
11.     else // In right subtree
    
12.         return findParent(n - 1, x - (1 >> (n - 1)) + 1);
    
13. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies