找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: pls331
收起左侧

[Facebook] Facebook Intern面经

[复制链接]

5

主题

4

精华

118

积分

资深会员

Rank: 2

积分
118
 楼主| 发表于 12-16-2016 11:36 AM | 显示全部楼层
Parent pointer的方法想到了。找到一个关键的parent, 只要找出从当前leaf往上的parent中,第一个走向左孩子的那个node,就是关键node.
4 ~: Y6 e: l" H* u% k关键node的右子树的最小孩子就是下一个。

4

主题

0

精华

59

积分

资深会员

Rank: 2

积分
59
发表于 12-16-2016 11:50 PM | 显示全部楼层
parent point 方法有点儿小难,学习了树的遍历竟然可以用O(1)的空间复杂度 厉害

5

主题

4

精华

118

积分

资深会员

Rank: 2

积分
118
 楼主| 发表于 12-17-2016 12:33 PM | 显示全部楼层
hlin77 发表于 12-7-2016 06:16 PM
5 q( R) j6 _( u1 z! R" J- o: J/ B用Morris Traversal, 每个有left child的node,他的predecessor用parent pointer连到这儿node,然后就能O( ...

( z! b! g" w+ C6 E+ g可以具体一点吗?Morris Traversal好像在哪儿听过。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表