【算法】一维数组构建二叉树细节优化

描述

在刷算法的时候，有一个一维数组构建二叉树有点争议。

就是我要这么一个二叉树：

然后chtgpt写的二叉树构建代码是这样的：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode buildTree(Integer[] nums) {
    return buildTree(nums, 0);
}

private TreeNode buildTree(Integer[] nums, int index) {
    if (index >= nums.length || nums[index] == null) return null;
    TreeNode node = new TreeNode(nums[index]);
    node.left = buildTree(nums, 2 * index + 1);
    node.right = buildTree(nums, 2 * index + 2);
    return node;
}

然后当输入：输入: [1,2,3,4,null,5,6,null,null,7]

的时候，7这个值被吞掉了。

分析

就gpt给出的这个【一维数组构建二叉树】是最原始的办法。

按他这个构建我要的二叉树，数组应该要这样：

[1,2,3,4,null,5,6,null,null,null,null,7]

因为他这个是严格按数组的下标去一一对应的。

很严格，只要是null的地方必须全部null起来。

哪怕父节点也是null，子节点也要两个null占位。

实现

基本实现：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode buildTree(Integer[] nums) {
    return buildTree(nums, 0);
}

private TreeNode buildTree(Integer[] nums, int index) {
    if (index >= nums.length || nums[index] == null) return null;
    TreeNode node = new TreeNode(nums[index]);
    node.left = buildTree(nums, 2 * index + 1);
    node.right = buildTree(nums, 2 * index + 2);
    return node;
}

优化一下：

public static TreeNode createBT(Integer[] arr){
	    if(arr.length == 0){
	        return null;
	    }
	    TreeNode root = new TreeNode(arr[0]);
	    Queue<TreeNode> queue = new LinkedList<>();
	    queue.add(root);

	    boolean isLeft = true;//是左子树
	    for(int i = 1; i< arr.length; i++){
	        TreeNode node = queue.peek(); //peek()获取第一个元素，不移除
	        if(isLeft){
	            if(arr[i] != null){
	                node.left = new TreeNode(arr[i]);
	                queue.offer(node.left); //offer(E e) 在队列尾部添加一个元素，并返回是否成功
	            }
	            isLeft = false;
	        } else {
	            if(arr[i] != null){
	                node.right = new TreeNode(arr[i]);
	                queue.offer(node.right);
	            }
	            //右节点加入队列尾部，删除第一个元素，保证队列里保存的是根节点
	            queue.poll(); //poll()  删除队列中第一个元素，并返回该元素的值,
	            isLeft = true;
	        }
	    }
	    return root;
	}

换了这个，才能用

输入: [1,2,3,4,null,5,6,null,null,7]

初始化出来我们想要的数组。

总结

这个优化学习一下。

要仔细看才能看懂。很巧妙