算法-广度优先搜索-二叉树的层序遍历&数组生成二叉树

二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
   
返回其层序遍历结果：
[
  [3],
  [9,20],
  [15,7]
]

树的定义：

publicclassTreeNode{int val;
    TreeNode left;
    TreeNode right;TreeNode(){}TreeNode(int val){this.val= val;}TreeNode(int val, TreeNode left, TreeNode right){this.val= val;this.left= left;this.right= right;}}

使用队列，并维护队列。

classSolution{public List<List<Integer>>levelOrder(TreeNode root){
        List<List<Integer>> res=newArrayList<List<Integer>>();if(root== null){return res;}
        LinkedList<TreeNode> queue=newLinkedList<>();
        queue.addLast(root);while(!queue.isEmpty()){// 单层的结果list
            List<Integer> level=newArrayList<>();// 每层的数量int size= queue.size();for(int i=0; i< size; i++){
                root= queue.removeFirst();
                level.add(root.val);// 左右子树入队列if(root.left!= null){
                    queue.addLast(root.left);}if(root.right!= null){
                    queue.addLast(root.right);}}
            res.add(level);}return res;}}

数组生成二叉树

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

public TreeNodelevelOrder(Integer[] input){
        TreeNode root=newTreeNode(input[0]);
        Queue<TreeNode> nodeQueue=newLinkedList<>();
        nodeQueue.add(root);int index=1;while(!nodeQueue.isEmpty()){
            TreeNode node= nodeQueue.remove();if(index== input.length){break;}

            Integer item= input[index++];if(item!= null){
                node.left=newTreeNode(item);
                nodeQueue.add(node.left);}if(index== input.length){break;}

            item= input[index++];if(item!= null){
                node.right=newTreeNode(item);
                nodeQueue.add(node.right);}}return root;}