s********u
发帖数: 1109 | 1 不是right sibling，而是right neighbor。
就是如果做BFS，与给定节点同一层的后面一个。给parent link，但没有root node，
也不能强行找到root之后然后再做BFS（本身那么做就非常低效）
======================================
没想出来，看了别人的思路写了一下，感觉写的非常冗余，不知道能不能优化一下：
TreeNode *findByLvl( TreeNode *root, int lvl ){
if( root == NULL )
return NULL;
if( lvl == 0 )
return root;
TreeNode *left = findByLvl(root->left,lvl+1);
if( left ) return left;
else return findByLvl(root->right,lvl+1);
}
TreeNode* rNeighbor( TreeNode *given ){
TreeNode *parent = given->parent;
int level = -1;
while(parent){
while( parent && parent->left != given ){
given = parent;
parent = given->parent;
level--;
}
if( parent == NULL )
return NULL;
TreeNode *local = findByLvl( parent->right, level + 1);
if(local)
return local;
else{
given = parent;
parent = given->parent;
level--;
}
}
return NULL;
} | l*n
发帖数: 529 | 2 怎么冗余啊，就是不停以不同的ancestor来找同样lvl的节点，已经是人脑识别模式了
。 |
|
