查看: 3569|回复: 24
收起左侧

求狗onsite高频题答案

|只看干货
匿名用户-8B3  2022-5-2 07:34:46 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2022(1-3月) 码农类General 硕士 全职@Google - 网上海投 - Onsite  | 🙁 Negative 😐 AverageOther | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
最近看到删除binary tree的leaf node的高频题。Followup1 要求新产生的leafnode最先被去‍‌‌‌‍‌‍‌‍‌‌‌‍‍‌‍‌‍‌‍除 (移除一个leaf他的parent变成leaf必须紧接着移除)

Followup2 要求新产生的leafnode最后被去除


我看followup1 类似是postorder的顺序,但还是不会。。。求指导下这两个followup


补充内容 (2022-05-02 22:51 +8:00):

followup2

您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
删除4,5后,删除3,再删除2,最后删除1

补充内容 (2022-05-03 01:19 +8:00):
原题类似366删除叶子节点,一层一层删,接着是两个followup

评分

参与人数 1大米 +4 收起 理由
清道神君 + 4

查看全部评分


上一篇:Twilio oa
下一篇:领英MLE电面

本帖被以下淘专辑推荐:

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   96% (885)
 
 
3% (33)    👎
本帖最后由 微信用户_e7fb7bf 于 2022-5-2 19:14 编辑
匿名者 发表于 2022-5-2 17:47
能讲一下followup1和2具体怎么做吗

follow up 1就是postorder traversal
  1. // Run in TypeScript Playground https://www.typescriptlang.org/play?#code/
复制代码
follow up 2 参考366的traversal 方式
------
不知道为啥code没发成功,详情见下
回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   95% (967)
 
 
4% (41)    👎
本帖最后由 sanmi0814 于 2022-5-2 11:33 编辑

不知楼主哪里不懂?
followup1 是postorder。先删除left,再删除right,这样left+right的parent 变leaf --> 马上需要被删. 这样顺序就是 left, right, root  i.e. postorder
followup2 给定一个tree,当前所有leaf需要先被删除,这些leaf的height是0  (因为没有在他们下面的node了)。
删除过程:
         1
       /      \
     2         3
/     \
4      5


4,5在delete_tree_leaf(2)下
4.left 4.right null--> height[0] = [4] --》 2 左height 1
5.left 5.right null--> height[0] = [4,5] --》2 右height 1
这样得到了2的height 1 把2放到height[1] = [2]


2和3在delete(1)下面
2 为1的左height,已经求得:1
3为1的右边height,需要求--》得到0--》 height[0]  [4,5,3]
这样得到1的height 1 + 1= 2
height[2] = [1]

所以最后就把所有height的list 合并一下height[0] + height[1] + height[2] = [4,5,3,  2,  1]



评分

参与人数 1大米 +1 收起 理由
xiaonany + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (885)
 
 
3% (33)    👎
  1. class TreeNode {
  2.     left: TreeNode | null;
  3.     right: TreeNode | null;
  4.     key: number | null;

  5.     constructor(key: number) {
  6.         this.key = key;
  7.         this.left = null;
  8.         this.right = null;
  9.     }

  10.     public postOrderSort(root: TreeNode | null, result: number[]) {
  11.         if (!root || !root.key) return
  12.         if (!root.left && !root.right) {
  13.             result.push(root.key)
  14.             return
  15.         }

  16.         this.postOrderSort(root.left, result);
  17.         this.postOrderSort(root.right, result);

  18.         if (root.left) {
  19.             root.left = null;
  20.         }

  21.         if (root.right) {
  22.             root.right = null;
  23.         }

  24.         if (!root.left && !root.right) {
  25.             result.push(root.key);
  26.         }

  27.         return
  28.     }
  29. }

  30. const root = new TreeNode(1);
  31. const node2 = new TreeNode(2);
  32. const node3 = new TreeNode(3);
  33. const node4 = new TreeNode(4);
  34. const node5 = new TreeNode(5);

  35. root.left = node2;
  36. root.left.left = node4;
  37. root.left.right = node5;
  38. root.right = node3;

  39. const result: number[] = []
  40. root.postOrderSort(root, result);
复制代码
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (1772)
 
 
6% (125)    👎
followup1就是postorder吧?followup2的话,要求感觉不是很明确,怎么定义“最后“?
回复

使用道具 举报

地里的匿名用户
匿名用户-8B3  2022-5-2 09:43:15
本楼: 👍   0% (0)
 
 
0% (0)   👎
yiliaobailiao 发表于 2022-5-1 18:03
followup1就是postorder吧?followup2的话,要求感觉不是很明确,怎么定义“最后“?

          1
       /      \
     2         3
/     \
4      5
删除4,5后,删除3,再删除2,最后删除1
回复

使用道具 举报

地里的匿名用户
匿名用户-FCE  2022-5-2 21:55:01
本楼: 👍   0% (0)
 
 
0% (0)   👎
本帖最后由 匿名 于 2022-5-2 09:58 编辑

能否请楼主把原题目说一下?问问题,原题不说……给一个tree,删除里面的leaf node,输出删除的顺序?
回复

使用道具 举报

地里的匿名用户
匿名用户-8B3  2022-5-2 22:52:07
本楼: 👍   0% (0)
 
 
0% (0)   👎
匿名者 发表于 2022-5-2 06:55
能否请楼主把原题目说一下?问问题,原题不说……给一个tree,删除里面的leaf node,输出删除的顺序?

是啊,输出删除顺序
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (446)
 
 
1% (8)    👎
本帖最后由 微信用户_0b7b21b 于 2022-5-2 11:19 编辑

results_remove_per_level 是按层剥离,results_remove_immediately是变成leaf node以后立刻删除def delete_tree_leaf(root):
    results_remove_immediately = []
    results_remove_per_level = []
    def post_order_delete(node):
        if not node:
            return -1
        left_level = post_order_delete(node.left)
        right_level = post_order_delete(node.right)
        cur_level = max(left_level, right_level) + 1
        if cur_level > len(results_remove_per_level) - 1:
            results_remove_per_level.append([])
        results_remove_per_level[cur_level].append(node.val)
        results_remove_immediately.append(node.val)
        return cur_level
    post_order_delete(root)
    return results_remove_per_level, results_remove_immediately

评分

参与人数 1大米 +1 收起 理由
terranzmczmx + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (885)
 
 
3% (33)    👎
这个原题的题干是什么楼主可以po一下吗,谢谢!
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   47% (86)
 
 
52% (94)    👎
我snoflake居然也被面了这个一毛一样的问题 ,但是多了个followup3
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (5)
 
 
0% (0)    👎
smileying 发表于 2022-5-2 16:11
我snoflake居然也被面了这个一毛一样的问题 ,但是多了个followup3

求问follow up 3?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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