面试题B2: 二叉树层序遍历与重建

package cn.zxy.interview.utils;

import java.util.LinkedList;

public class UtilsTree {
    /**
     * 根据层序遍历 生成二叉树
     * @param arr
     * @return
     */
    public static TreeNode arrayToTree(Integer[] arr){
        //使用队列遍历二叉树  队列的使用offer(加入新节点)/poll(返回并删除队首元素)
        LinkedList<TreeNode> queue = new LinkedList<>();

        //创建根节点
        TreeNode root = new TreeNode(arr[0]);
        //节点入队列
        queue.push(root);

        int i = 1;
        while(i < arr.length){
            //从数组中取出值
            Integer value = arr[i];
            //从队列中弹出元素
            TreeNode node = queue.poll();
            if(value != null){
                //创建左孩子节点, 放入队列, 填充value
                TreeNode leftNode = new TreeNode(value);
                queue.offer(leftNode);
                node.left = leftNode;
            }
            // 取出数组下一个元素
            i++;
            if(i >= arr.length) break;
            value = arr[i];

            if(value != null){
                //创建右孩子
                TreeNode rightNode = new TreeNode(value);
                queue.offer(rightNode);
                node.right = rightNode;
            }
            i++;
        }
        return root;
    }

    public static void levelOrderShow(TreeNode root){
        //1.创建队列, 用于存储节点
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //2.初始化 根节点入队列
        queue.offer(root);

        //3.从队列中取元素 只要只要队列不为空, 就继续进行迭代
        while(!queue.isEmpty()){
            //从队列中取出节点
            TreeNode node = queue.poll();
            System.out.println(node.value);
            //检查左右孩子节点 如果有 入队列
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
    }
    

    public static void main(String[] args) {
        Integer[] arr = {3,4,5,1,2,6,1};
        TreeNode root = arrayToTree(arr);
        levelOrderShow(root);

    }
}