2021.03.31 伴鱼 java 春招 一面

手写算法

第一题是按层次遍历二叉树，第一层从左到右第二层从右到左，以此类推。二叉树利用数组输入。

我的想法是既然是用数组输入，那么可以当作完全二叉树处理，为0就跳过。不为0就视为当前结点存在，完全二叉树的话就可以通过当前深度确定每一层的边界即最左结点和最右结点，第一层循环对深度遍历，第二层循环对这一层的每一个结点遍历，通过深度对2取余的结果作为第二层循环是++还是--。但是面试官说我的想法有问题，让我用队列做，没想出来，就换了一道题。

第二题是leetcode上的原题，空间复杂度o(1)判断链表是否为回文链表。

面试的规则是半小时内写出来一道题，不会可以换题，但时间不会重置。公司效率很高，面完不到10分钟，还没跟舍友吐槽完，hr的电话就来了，爱了爱了。