databricks电面挂经

一个亚裔小哥面的， 之前就把LC上tag题做了下，他家流程非常长。一轮电面一轮3小时task一轮HR面最后再是4轮onsite。题目是

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这题之前没做过面试时没做出来。move on了。

请问他会给你你root node吗？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主能解释下，直接dfs遍历是O1空间吗，parent node有什么用呢

Rootuny 发表于 2020-8-30 12:14
楼主能解释下，直接dfs遍历是O1空间吗，parent node有什么用呢

dfs遍历需要stack是O(n)

这题好难啊

这是一个用O(1) space做level order traversal的问题。假设binary tree的深度为d，可以做d次Morris traversal，第i次遍历只打印深度为i的节点。虽然space是O(1)的，但是最坏情况下时间复杂度是O(n^2)。这是我能想出满足要求的最优解法了。