leetcode根据数组创建一棵二叉树(用于测试)

最近一直在刷题,很多树的题目,用例都是一个数组,这样的话自己测试起来就比较麻烦,所以自己写 了一个工具类,专门用于生成测试用的二叉树。

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

对应的数组是:{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}
我的思路参考了这篇文档:https://blog.csdn.net/lenfranky/article/details/84444816
具体思路:利用层次遍历的思想,根据上一层的非空节点pre,创建下一层的节点,创建下一层节点点的时候,将下一层的非空节点放到一个新的队列cur里面,这里有一个需要注意的点是,当超过了数组的下标以后,剩下的所有节点的左右子树都是空了。
具体代码如下:

public class TreeUtil {

    public static TreeNode createTree(Integer[] arr) {
        // 使用队列来存储每一层的非空节点,下一层的数目要比上一层高
        ArrayDeque<TreeNode> pre = new ArrayDeque<>();
        TreeNode root = new TreeNode(arr[0]);
        pre.addLast(root);
        // 表示要遍历的下一个节点
        int index = 0;
        while (!pre.isEmpty()) {

            ArrayDeque<TreeNode> cur = new ArrayDeque<>();
            while (!pre.isEmpty()) {
                TreeNode node = pre.removeFirst();
                TreeNode left=null;
                TreeNode right=null;
                // 如果对应索引上的数组不为空的话就创建一个节点,进行判断的时候,
                // 要先索引看是否已经超过数组的长度,如果索引已经超过了数组的长度,那么剩下节点的左右子节点就都是空了
                // 这里index每次都会增加,实际上是不必要的,但是这样写比较简单
                if (++index<arr.length&&arr[index]!=null){
                    left=new TreeNode(arr[index]);
                    cur.addLast(left);
                }
                if (++index<arr.length&&arr[index]!=null){
                    right=new TreeNode(arr[index]);
                    cur.addLast(right);
                }
                node.left=left;
                node.right=right;
            }
            pre=cur;
        }


        return root;
    }

    public static void main(String[] args) {
        //Integer[] arr = {5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1};
        Integer[] arr={5,4};
        TreeNode tree = createTree(arr);
        prePrinTree(tree);

    }

    private static void prePrinTree(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        prePrinTree(node.left);
        prePrinTree(node.right);
    }
}
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

版权声明:本文为dream_follower原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>