一个题：给定一个节点，找right neighbor# JobHunting - 待字闺中
s*u
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;
}
就是如果做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;
}