Java⼀维数组转换⼆叉树结构最近在Leetcode刷题，发现遇到不少⼆叉树类型的题⽬，题⽬会定义好树节点TreeNode的数据结构。 1public class TreeNode {
2int val;
3    TreeNode left;
4    TreeNode right;
5    TreeNode() {}
6    TreeNode(int val) { this.val = val; }
7    TreeNode(int val, TreeNode left, TreeNode right) {
8this.val = val;
9this.left = left;
10this.right = right;
11    }
12 }
在题⽬的⽰例中，⼆叉树的输⼊都是⼀个⼀维数组，表⽰这个⼆叉树结构。
例如：
输⼊：root = [3,1,4,3,null,1,5]
表⽰的⼆叉树为：
因此在IDE⾥⾯编码调试时，需要⼀个转化⽅法⽅便⾃⼰编写并运⾏测试⽤例。
简单分析数组和⼆叉树之间的关系：
输⼊：root = [1,2,3,4,5,6,7,8,9]
第i个节点的左⼦节点为第2*i个节点，右⼦节点为第2*i+1个节点。因此⽤简单的递归就可以实现。
1public class TreeNodeUtil {
2public static TreeNode createTreeNode(Integer[] array){
3        TreeNode root = createTreeNode(array, 1);
4return root;
5    }
6
java定义一维数组并赋值7private static TreeNode createTreeNode(Integer[] array, int index) {
8if(index > array.length){
9return null;
10        }
11        Integer value = array[index - 1];
12if(value == null){
13return null;
14        }
15        TreeNode node = new TreeNode(value);
16        node.left = createTreeNode(array, index * 2);
17        node.right = createTreeNode(array, index * 2 + 1);
18return node;
19    }
20 }
但是这个⽅法对于⼀些情况却转化错误。因为这个⼀维数组是优化后的。
例如：
按照上⾯⽅法，输⼊应该为：
输⼊：root = [2,null,4,null,null,9,8,null,null,null,null,null,null,4]
空⼦节点下没有⼦节点，因此不需要这么多冗余数据。
因此输⼊应该为：
输⼊：root = [2,null,4,9,8,null,null,4]
再次分析数组和⼆叉树之间的关系，发现数组中的数据顺序是按照⼆叉树的层级排列的，这时可以使⽤队列的数据结构，数组中的节点按顺序进队，每次节点出队，如果不是空节点，那么紧跟着是该节点的左⼦节点和右⼦节点。
1public class TreeNodeUtil {
2public static TreeNode arrayToTreeNode(Integer[] array){
3if(array.length == 0){
4return null;
5        }
6        TreeNode root = new TreeNode(array[0]);
7        Queue<TreeNode> queue = new LinkedList<>();
8        queue.add(root);
9boolean isLeft = true;
10for(int i = 1; i < array.length; i++){
11            TreeNode node = queue.peek();
12if(isLeft){
13if(array[i] != null){
14                    node.left = new TreeNode(array[i]);
15                    queue.offer(node.left);
16                }
17                isLeft = false;
18            }else {
19if(array[i] != null){
20                    node.right = new TreeNode(array[i]);
21                    queue.offer(node.right);
22                }
23                queue.poll();
24                isLeft = true;
25            }
26        }
27return root;
28    }
29 }
这样，⼀维数组转换成⼆叉树就完成了！输⼊⼀个⼀维数组，返回⼆叉树的根节点。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。