一个题：给定一个节点，找right neighbor

发信人: smilenceyu (smilence), 信区: JobHunting
标  题: 一个题：给定一个节点，找right neighbor
发信站: BBS 未名空间站 (Fri Oct 11 22:37:56 2013, 美东)

不是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;
       
}
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 71.]

http://www.mitbbs.com/article_t/JobHunting/32552365.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

金士顿26周年，买U盘抽奖送笔记本电脑 ， 更多京东优惠券