笔试的时候肯定得自己构造二叉树，但我们平常刷 LeetCode 的话基本都不会涉及到自己构建这块，所以这块其实还是很重要但是又容易被忽视的。

二叉树节点的定义如下：

// 定义二叉树节点
static class TreeNode {
    private int val;
    private TreeNode left;
    private TreeNode right;

    public TreeNode (int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

构建方法 1

下面这套代码对应根据满二叉树层序遍历的结果进行构建：

笔试题一般都是这种构建方法

public class BuildTree {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // str 是满二叉树层序遍历的节点数组（包含 null）
        // ex:1,4,3,1,null,2,null,null,null,null,null,1,null,null,null]
        String[] str = sc.nextLine().split(",");
        TreeNode root = buildTree(str);
        System.out.println("");
    }

    private static TreeNode buildTree(String[] str) {
        if (str == null || str.length == 0) {
            return null;
        }

        // 构造 TreeNode 集合
        List<TreeNode> list = new ArrayList<>();
        for (String node : str) {
            list.add(node.equals("null") ? null : new TreeNode(Integer.parseInt(node)));
        }

        for (int i = 0; i < list.size() / 2; i ++) {
            TreeNode cur = list.get(i);
            // cur == null 的话，那他的左右孩子也就不需要处理了
            if (cur == null) {
                continue;
            }
            cur.left = list.get(i * 2 + 1);
            cur.right = list.get(i * 2 + 2);
        }

        return list.get(0);
    }

    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
}

构建方法 2

如下图，这种格式也是按照的层序遍历的顺序，不过和上面所说的满二叉树格式不同，具体区别就是：如果某个节点是 null 的，那么它的左右孩子节点是不会出现在遍历结果的，举个例子：

所以我们就没有办法像上题一样基于下标来构建了，需要借助层次遍历的队列来进行

public class BuildTree {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // ex: 1,4,3,1,null,2,null,null,null,1,null
        String[] str = sc.nextLine().split(",");
        TreeNode root = buildTree(str);
        System.out.println("");
    }

    private static TreeNode buildTree(String[] str) {
        if (str == null || str.length == 0) {
            return null;
        }

        // 构造 TreeNode 集合
        List<TreeNode> list = new ArrayList<>();
        for (String node : str) {
            list.add(node.equals("null") ? null : new TreeNode(Integer.parseInt(node)));
        }

        TreeNode root = list.get(0);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // i 指向当前节点 cur 的左子树节点
        int i = 1;
        while (!queue.isEmpty() && i < str.length) {
            TreeNode cur = queue.poll();
            // 此处不需要进行 cur 的判空，因为队列中不会存储 null 的节点

            // cur 的左（i）孩子入队
            cur.left = list.get(i);
            if (cur.left != null) {
                // cur.left == null 的话，那么 cur.left 的左右孩子也一定为 null，就不用入队构建了
                queue.offer(cur.left);
            }
            // cur 的右（i + 1）孩子入队
            cur.right = list.get(i + 1);
            if (cur.right != null) {
                // cur.right == null 的话，那么 cur.right 的左右孩子也一定为 null，就不用入队构建了
                queue.offer(cur.right);
            }

            // 进入下一个节点的左子树节点
            i += 2;
        }
        
        return root;
    }

}

构建方法 3

下面这套构建二叉树的代码对应如下的输入格式：

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch 同理)

示例

输入
1 2 3
2 4 5
4 0 0
5 0 0
3 6 7
6 0 0

【具体代码】：

// 构造二叉树
private static TreeNode createTree(Scanner sc) {
    String[] values = sc.nextLine().split(" ");
    if (values.length < 3) {
        return null;
    }

    int value = Integer.parseInt(values[0]);
    int left = Integer.parseInt(values[1]);
    int right = Integer.parseInt(values[2]);

    TreeNode root = new TreeNode(value);
    if (left != 0) {
        root.left = createTree(sc);
    }
    if (right != 0) {
        root.right = createTree(sc);
    }

    return root;
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    sc.nextLine(); // 第一行没啥用
    TreeNode root = createTree(sc);
}