可能是在刷招聘时顺手打了招呼，在 BOSS 直聘上跟朗致集团HR聊了几句，大致介绍了面试流程，说要有线上评测和远程写代码。我觉得没有什么问题，于是就安排上了。

面试过程

先是预订了晚八点的线上评测。我以为是开发技术知识，大概会考些基础选择题。没有想到是类似公考的思维逻辑题目。有些题目的题干只有两三句话，我反复阅读多遍都没有理解其字面意思。答完问卷星上的25个题目，实时名次我排第二名。看了看视频会议室里的诸位候选人，大家都一副怀疑人生的表情。

不久在企业微信上接到了远程代码面试的通知，还贴心地给出了大致范围，即链表与算法，建议用心准备。面试官还会提前联系，测试会议室软件。面试前，随便翻了两篇文章。时间一到，我拿着一台新笔记本电脑，就近找了一家饮品店，点了饮料就开始了。

有一点不太适应新笔记本电脑上的新环境，紧张到一开始代码少了一个括号，都花了好几分钟才定位到。面试官很 Nice，并没有催促。

现场敲代码

双向链表的基础结构

@Data
public Node<T>{
    private T value;
    private Node<T> prev;
    private Node<T> next;
}

三向链表（二叉树）

@Data
public Node<T>{
    private T value;
    private Node<T> parent;
    private Node<T> left;
    private Node<T> right;
}

创建指定高度的满二叉树

饮品店的柜台的服务员正忙着出单，锅碗叮咣乱响。和面试官对话都听不太清，思路很乱。最后在面试官的引导下，用调试模式看了一下，修正了一下 level 与层高的问题。这个问题算是过了。

public class Test{
    public static Node<Integer> build(int level){
        Node<Integer> root = new Node<>();
        buildChild(root, level - 1);
        return root;
    }

    public static <T> void buildChild(Node<T> parent, int level){
        Node<T> left = new Node<T>();
        Node<T> right = new Node<T>();

        parent.setLeft(left);
        parent.setRight(right);

        left.setParent(parent);
        right.setParent(parent);

        if(level > 1){
            buildChild(left, level - 1);
            buildChild(right, level - 1);
        }
    }
}

在创建时准确赋值

如图所示，给满二叉树的各个节点，逐层准确赋值。在此前代码基础上，在构建树的同时进行赋值。

flowchart TD A1((1))-->B1((2)) A1-->B2((3)) B1-->C1((4)) B1-->C2((5)) B2-->C3((6)) B2-->C4((7))

我一看我前面用的是递归，相当于用“前序”的顺序创建了各个节点，怎么可能在构建树的同时进行精准赋值呢？首先，要继续前面代码的思路，第二要保证实现目标需求，于是脑袋一热，思路一拧，打算按层级遍历，逐个按顺序赋值。

明知这是个笨办法，虽然适用范围更广，题目中既然是满二叉树，自然应该有更简明的办法，但还是硬着头皮写下去。因为一行代码放错了位置，应该在循环外；在面试官盯着的压力下，试图打印有问题的部分，暴力调试来解决问题。在最后的10分钟，还是纠结于实现通用的逐层遍历方法。最终没有输出正确结果。面试就结束了。

然后我找了个安静的地方，看了一下刚才的代码，只要改一行就 OK 了。正确的版本：

public static Node<Integer> build(int level){
    Node<Integer> root = new Node<>();
    buildChild(root, level - 1);
    Node<Integer>[] currentLevelNodes = new Node[]{root};

    int value = 1;
    for (int i = 1; i <= level; i++) {
        Node<Integer>[] nextLevelNodes = new Node[currentLevelNodes.length * 2];

        for (int j = 0; j < currentLevelNodes.length; j++) {
            currentLevelNodes[j].setValue(value++);
            nextLevelNodes[j * 2] = currentLevelNodes[j].getLeft();
            nextLevelNodes[j * 2 + 1] = currentLevelNodes[j].getRight();
        }
        currentLevelNodes = nextLevelNodes;
    }
    return root;
}

然而满二叉数是一种极特殊的情况，若根节点编号是 i，它的左子节点的索引则是 i*2，右子节点的索引是 i*2 + 1。但当处于紧张状态时，认为距离胜利就差一点点，根本不愿尝试其他思路和方式。其实整个题目只是需要创建一个这样的方法：

private static Node<Integer> createFullBinaryTree(int depth, int index) {
    if (depth <= 0) {
        return null;
    }
    Node<Integer> node = new Node<>();
    node.setValue(index);

    Node<Integer> left = createFullBinaryTree(depth - 1, index * 2);
    Node<Integer> right = createFullBinaryTree(depth - 1, index * 2 + 1);

    node.setLeft(left);
    node.setRight(right);

    if (left != null) {
        left.setParent(node);
    }
    if (right != null) {
        right.setParent(node);
    }
    return node;
}

思路不通畅，就不要硬推进度。所谓欲速则不达。

后续问题

据网友们说，后面还有一个面试问题：在不重复遍历、不额外使用存储空间的情况下，从任意节点出发打印整棵树。这个部分代码就略了，大致只需向下打印该节点的左右节点，向上打印父节点，以及向下打印兄弟节点即可。

关于面试的讨论

自己在面试时表现得浑浑噩噩，不禁好奇其他人的面试过程。在朗致集团有人听说过吗？问题的回答中，有批评面试的，有批评公司的。反正也是莫名就参加了面试，释然了。

结语

我很纳闷，面试结束前的那几分钟地狱时刻，我都一直没有决定试试只要一分钟写完的第二种写法。果然，有点理解那些面试时碰到手搓接雨水问题的同行们的怨念了。