填充树的next指针

populating-next-right-pointers-in-each-node

http://www.nowcoder.com/questionTerminal/fdbd05d647084fcf9be78444e231998b

用层次遍历很好做的,但是题目要求是常数级别的空间复杂度,因此需要转换思路。

我们发现:

  1. 如果设当前层为i,且当前层所有节点的next指针都已经填充,则从第i层的最左边节点出发,可以遍历当前层;
  2. 设当前节点为第i层的第j个节点,那么很容易就能填充节点j在第i+1层的子节点的next指针

于是,产生了如下代码(如果觉得理解不了,可以画画图):

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode *left = root;
        while(left->left) {
            TreeLinkNode *p = left;
            while (p) {
                p->left->next = p->right;
                if (p->next) p->right->next = p->next->left;
                p = p->next;
            }
            left = left->left;
        }
    }
};
刷遍天下无敌手 文章被收录于专栏

秋招刷题历程

全部评论

相关推荐

昨天 23:26
河南大学 Java
双非本,刚学完Redis,项目只有外卖和点评,八股没准备,算法只有lqb省一,感觉敲的项目也是一言难尽没怎么吸收。怎么你们都有实习了
大牛之途:27急个锤子,你投日常实习最好的时间就是9,10月份,那时候暑期实习都结束了,正是缺人的时候。这份日常又能给你的暑期实习增加竞争力,暑期找的好了秋招也不怕了,都是环环相扣的
点赞 评论 收藏
分享
喜欢喜欢喜欢:这是我见过最长最臭的简历
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务