这段时间时不时地会在leetcode上做些题，最近做到的大部分是与树相关的题。由于是在本地的IDE上码代码，如果每次测试都要到leetcode上来测的话，不仅要选中复制粘贴一遍，而且每次测试还要读一会条，一次两次还好，次数多了还是比较烦。而如果在本地的类内的main()函数里测试的话，每次构建一个树也比较麻烦，而且仅仅更换数值还好，若要更换树的结构，那工程量就有点大了。

所以在这里准备写一个创建树的函数来解决这个问题，后面做起题来效率也能高一些。

话不多说，下面先直接放上所用的代码：

本例中所构建的树的结构      5     / \    4   8   /   / \  11  13  4 /  \      \7    2      1

package learning_java;import LeetCode.TreeNode;import java.util.Deque;import java.util.LinkedList;public class ConstructTree {
        public static TreeNode constructTree(Integer[] nums){
            if (nums.length == 0) return new TreeNode(0);        Deque
    
      nodeQueue = new LinkedList<>();        // 创建一个根节点        TreeNode root = new TreeNode(nums[0]);        nodeQueue.offer(root);        TreeNode cur;        // 记录当前行节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2）        int lineNodeNum = 2;        // 记录当前行中数字在数组中的开始位置        int startIndex = 1;        // 记录数组中剩余的元素的数量        int restLength = nums.length - 1;        while(restLength > 0) {
                // 只有最后一行可以不满，其余行必须是满的//            // 若输入的数组的数量是错误的，直接跳出程序//            if (restLength < lineNodeNum) {
    //                System.out.println("Wrong Input!");//                return new TreeNode(0);//            }            for (int i = startIndex; i < startIndex + lineNodeNum; i = i + 2) {
                    // 说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root                if (i == nums.length) return root;                cur = nodeQueue.poll();                if (nums[i] != null) {
                        cur.left = new TreeNode(nums[i]);                    nodeQueue.offer(cur.left);                }                // 同上，说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root                if (i + 1 == nums.length) return root;                if (nums[i + 1] != null) {
                        cur.right = new TreeNode(nums[i + 1]);                    nodeQueue.offer(cur.right);                }            }            startIndex += lineNodeNum;            restLength -= lineNodeNum;            lineNodeNum = nodeQueue.size() * 2;        }        return root;    }    public static void main(String[] args) {
            Integer[] nums = {
    5,4,8,11,null,13,4,7,2,null,null,null,1};        TreeNode root = ConstructTree.constructTree(nums);        System.out.println(root);    }}
    

使用时，像上面main()方法中一样，只需要调用类内的静态方法constructTree(Integer[] nums)，输入的参量为一个整型的数组，数组中的元素是按层次遍历的二叉树的值（若某节点在下一层中的某个儿子或两个儿子为空，则在下一层的这一个或两个位置填null），与Leetcode中树的表示方法相同，即可以直接把Leetcode上的测试用例按它的形式拖过来直接使用。

简单解释一下所用的方法，核心思想是在每一层，用一个队列nodeQueue来存储该层的所有节点，然后用父节点的数量的两倍来遍历输入的数组（从上一层结束的地方开始），并从队列中取出（位于上一层的）对应的父节点（此时已从队列中删去，因为用的方法为poll()而不是peek()），对于每一个值，创建相应的子节点链接到父节点，并加入到队列中，依次不断循环，直到遍历完整个数组。

这里一个踩过的坑是，其中因为一部分数值为null，而如果用int基本类型的数组的话，数组内是不能用null的，因此这里用了int的包装类Integer的数组来作为传入的参数的声明。

最后，让我们测试一下我们的代码，测试用的树与上面一样，测试中我们采用先序遍历来进行输出，查看结果是否正确：

/*用于测试的树，与上例中相同      5     / \    4   8   /   / \  11  13  4 /  \      \7    2      1 */package learning_java.sortTry;import LeetCode.TreeNode;import learning_java.ConstructTree;public class ConstructTreeTest {
        public void preOrder(TreeNode root) {
            if (root == null) return;        System.out.print(root.val + " ");        preOrder(root.left);        preOrder(root.right);    }    public static void main(String[] args) {
            Integer[] nums = {
    5,4,8,11,null,13,4,7,2,null,null,null,1};        TreeNode root = ConstructTree.constructTree(nums);        new ConstructTreeTest().preOrder(root);    }}

测试结果：

5 4 11 7 2 8 13 4 1

可以看到，我们得到了一棵所需要的树。

更新

在实际使用中发现，leetcode中所给的case经常并不是标准的个数，最后一行往往是不满的，如

5     /     4

这样一棵树，给出的数组中仅有两个数字：[5, 4]，即最后一行中的末尾的null会被舍弃，因此，在我们的程序中，应在遍历过程中加入停止条件（更严谨的方式是保存判定错误输入的条件，并仅在树的最后一行的遍历过程中进行停止判定）。