如何通过接收数组参数的构造器逐层从左到右构建二叉树

问题分析 #

你原有代码的核心问题是递归逻辑判断条件错误：root == null的限制导致只有首次创建根节点时会进入逻辑，后续递归创建子节点时root已经初始化，不会执行子节点创建逻辑，同时对入参node的处理和返回值逻辑也完全不符合递归构建子树的要求。

修正后实现 #

public BinaryTree(Object... args) {
    // 直接把递归生成的根节点赋值给成员变量root
    this.root = makeBinaryTree(args, 0);
}

// 调整递归方法参数，只需要传入数组和当前节点对应的索引即可，返回当前索引位置生成的节点
private Node makeBinaryTree(Object[] args, int index) {
    Node node = null;
    // 索引合法，且当前位置元素不为空的情况下才创建节点
    if (index < args.length && args[index] != null) {
        node = new Node(args[index]);
        // 递归创建左子树：索引为 2*index +1
        node.setLeft(makeBinaryTree(args, 2 * index + 1));
        // 递归创建右子树：索引为 2*index +2
        node.setRight(makeBinaryTree(args, 2 * index + 2));
    }
    return node;
}

验证说明 #

1. 调用new BinaryTree(1,2,3,4,5,6)时：
   索引0对应根节点1，左子节点索引1是2，右子节点索引2是3；
   节点2的左索引3是4、右索引4是5；
   节点3的左索引5是6，右索引6超出数组长度返回null，完全符合你第一个预期的树结构。
2. 如果你要实现第二个示例中3的右节点是7，左节点为空的结构，需要在对应空节点的位置传入null，即调用new BinaryTree(1,2,3,4,5,null,7)，此时索引5的元素是null不会生成节点，索引6的元素是7会生成3的右节点，和你的第二个预期结构完全一致。

内容的提问来源于stack exchange，提问作者Fire Assassin