Java一维数组转换二叉树结构

2021-01-19 17:16

阅读：527

标签：使用简单 color poll 目的 isl 递归运行 node

最近在Leetcode刷题，发现遇到不少二叉树类型的题目，题目会定义好树节点TreeNode的数据结构。

 1 public class TreeNode {
 2     int val;
 3     TreeNode left;
 4     TreeNode right;
 5     TreeNode() {}
 6     TreeNode(int val) { this.val = val; }
 7     TreeNode(int val, TreeNode left, TreeNode right) {
 8         this.val = val;
 9         this.left = left;
10         this.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个节点。因此用简单的递归就可以实现。

 1 public class TreeNodeUtil {
 2     public static TreeNode createTreeNode(Integer[] array){
 3         TreeNode root = createTreeNode(array, 1);
 4         return root;
 5     }
 6 
 7     private static TreeNode createTreeNode(Integer[] array, int index) {
 8         if(index > array.length){
 9             return null;
10         }
11         Integer value = array[index - 1];
12         if(value == null){
13             return null;
14         }
15         TreeNode node = new TreeNode(value);
16         node.left = createTreeNode(array, index * 2);
17         node.right = createTreeNode(array, index * 2 + 1);
18         return 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]

再次分析数组和二叉树之间的关系，发现数组中的数据顺序是按照二叉树的层级排列的，这时可以使用队列的数据结构，数组中的节点按顺序进队，每次节点出队，如果不是空节点，那么紧跟着是该节点的左子节点和右子节点。

 1 public class TreeNodeUtil {
 2     public static TreeNode arrayToTreeNode(Integer[] array){
 3         if(array.length == 0){
 4             return null;
 5         }
 6         TreeNode root = new TreeNode(array[0]);
 7         Queue queue = new LinkedList();
 8         queue.add(root);
 9         boolean isLeft = true;
10         for(int i = 1; i ){
11             TreeNode node = queue.peek();
12             if(isLeft){
13                 if(array[i] != null){
14                     node.left = new TreeNode(array[i]);
15                     queue.offer(node.left);
16                 }
17                 isLeft = false;
18             }else {
19                 if(array[i] != null){
20                     node.right = new TreeNode(array[i]);
21                     queue.offer(node.right);
22                 }
23                 queue.poll();
24                 isLeft = true;
25             }
26         }
27         return root;
28     }
29 }

这样，一维数组转换成二叉树就完成了！输入一个一维数组，返回二叉树的根节点。

Java一维数组转换二叉树结构

标签：使用简单 color poll 目的 isl 递归运行 node

原文地址：https://www.cnblogs.com/ghimtim/p/12905792.html

上一篇：排序NB三人组（快速排序/堆排序/归并排序）

下一篇：用VS Code写Python

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Java一维数组转换二叉树结构
文章链接：http://soscw.com/index.php/essay/44163.html

亲，登录后才可以留言！

Java一维数组转换二叉树结构

评论

热门文章

推荐文章

最新文章

置顶文章