用三向链表根据输入的数字n, 构建深度为n的满二叉树， 此算法怎么解？

Question

面试遇到一算法题，题目是：“用三向链表根据输入的数字n, 构建深度为n的满二叉树”，面试官要求十分钟内写出此算法，结果凉凉。 后续在网上也没有找到相关的解题思路，在此求助各位大神，此算法应该如何写？

三向链表对象如下：

public class ListNode<T> {
     T val;
     ListNode parent;
     ListNode childLeft;
     ListNode childRight;
}

Answer 1

递归构建结点即可，参考代码：

public static Node<Integer> build(Node<Integer> parent, int val, int depth) {
    Node<Integer> node = new Node<>();
    node.parent = parent;
    node.val = val;
    if (--depth > 0) {
        node.childLeft = build(node, val *= 2, depth);
        node.childRight = build(node, val + 1, depth);
    }
    return node;
}

另一个参考代码是将结点连接交给构造函数处理，build 负责递归即可：

public class Node<T> {

    T val;
    Node<T> parent;
    Node<T> childLeft;
    Node<T> childRight;

    public Node(T val, Node<T> childLeft, Node<T> childRight) {
        this.val = val;
        this.childLeft = childLeft;
        this.childRight = childRight;
        if (childLeft != null) childLeft.parent = this;
        if (childRight != null) childRight.parent = this;
    }

    @Override
    public String toString() {
        return val.toString();
    }

}

public class Test {

    public static Node<Integer> build(int val, int depth) {
        return depth > 0 ? new Node<>(val, build(val *= 2, --depth), build(val + 1, depth)) : null;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("depth(>=1): ");
        int depth = in.nextInt();

        Node<Integer> node = build(1, depth);

        Queue<Node<Integer>> q = new ArrayDeque<>();
        while (node != null) {
            System.out.println(node.parent + " --> " + node);
            if (node.childLeft != null) q.offer(node.childLeft);
            if (node.childRight != null) q.offer(node.childRight);
            node = q.poll();
        }
    }

}

depth(>=1): 3
null --> 1
1 --> 2
1 --> 3
2 --> 4
2 --> 5
3 --> 6
3 --> 7

graph TD
1((1)) --- 2((2))
1 --- 3((3))
2 --- 4((4))
2 --- 5((5))
3 --- 6((6))
3 --- 7((7))