BM26 求二叉树的层序遍历（变形更新中）

Bertha 。 2023-10-04 17:41 34阅读 0赞

### 描述 ###

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）  
例如：  
给定的二叉树是\{3,9,20,\#,\#,15,7\},

![7698725d6a525c59026575da476f9189.png][]

该二叉树层序遍历的结果是  
\[  
\[3\],  
\[9,20\],  
\[15,7\]

提示:

0 <= 二叉树的结点数 <= 1500

示例1

输入：

{1,2}

返回值：

[[1],[2]]

示例2

输入：

{1,2,3,4,#,#,5}

返回值：

[[1],[2,3],[4,5]]

**代码：**

**复杂度分析：**  
时间复杂度：*O(n)*,每个点进队出队各一次，遍历了整个二叉树。  
空间复杂度：*O(n)*,队列中元素的个数不超过 n 个，所以空间复杂度为 O(n)。

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    import java.util.Deque;
    public class Solution {
        /**
         * 
         * @param root TreeNode类 
         * @return int整型ArrayList<ArrayList<>>
         */
        public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
            // write code here
            Deque<TreeNode> dq=new LinkedList<>();
            ArrayList<ArrayList<Integer>> al=new ArrayList<ArrayList<Integer>>();
             if(root==null){
                return al;
            }
            dq.offer(root);  //进队列
            while(!dq.isEmpty()){
                ArrayList<Integer> list=new ArrayList<>();  //临时存储该层节点
                int size=dq.size(); //这一层有多少个节点
                for(int i=0;i<size;i++){
                    TreeNode temp=dq.peek();  //取队列第一个节点
                    list.add(temp.val); //将队列出的节点值存储到list中
                    dq.poll();  //出队列
                    if(temp.left!=null){
                        dq.offer(temp.left);
                    }
                    if(temp.right!=null){
                        dq.offer(temp.right);
                    }
                 }
                 al.add(list);  //将这一层的所有的节点全部存储到一个总的list中
            }
            return al;
        }
    }

## 变形一 ##

### BM35 判断是不是完全二叉树 ###

### 描述 ###

给定一个二叉树，确定他是否是一个完全二叉树。

完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 \[1~2h\] 个节点）

数据范围：节点数满足1≤n≤100

样例图1：

![21c756ecee5382a5e8f38e68100fd5fd.png][]

样例图2：

![e388429f776c3e849db1e50652139d28.png][]

示例1

输入：

{1,2,3,4,5,6}

返回值：

true

示例2

输入：

{1,2,3,4,5,6,7}

返回值：

true

###  ###

### 题解： ###

**思路：借助层序遍历**

只有`x,x,x,#,#,#`这样的才是完全二叉树

如果出现`x,#,y,#,#,#`或者`x,#,#,x,#,#,#`证明不是完全二叉树

碰到第一个\#的时侯令`flag=true`

如果再次碰到非`#`结点，且`flag=true`时候，说明不是完全二叉

![a653a1c4ba59e993029500d6ccca1c05.gif][]

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     *   public TreeNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param root TreeNode类 
         * @return bool布尔型
         */
        public boolean isCompleteTree (TreeNode root) {
            // write code here
            if(root==null)
                return true;
            Deque<TreeNode> dq=new LinkedList<>();
            dq.offer(root);
            boolean flag=false;  //这个flag用来判断前面是否已经有空节点
            boolean res=true;
            while(!dq.isEmpty()){
                int size=dq.size();
                for(int i=0;i<size;i++){
                    TreeNode temp=dq.poll();
                    if(temp==null){  //由于进入队列没有判别左右子树是否为空，所以可能是空值
                       //这里表示当前的节点为空，则如果后面还有节点的话，则不是一颗二叉树 
                        flag=true;  //该节点为空
                    }else{  //该节点不为空
                        if(flag){    //前面已经出现了空节点，后面如果还有节点，则直接返回不是二叉树
                            return false;
                        }
                        dq.offer(temp.left);  //不管该节点的左右节点是否为空，都进入了队列
                        dq.offer(temp.right);  //不管该节点的左右节点是否为空，都进入了队列
                    }
                }
            }
            return true;  //遍历完，是完全二叉树
        }
    }

## 变形二 ##

### BM41 输出二叉树的右视图 ###

### 描述 ###

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

数据范围： 0≤n≤10000  
要求： 空间复杂度 O(n)，时间复杂度 O(n)

如输入\[1,2,4,5,3\],\[4,2,5,1,3\]时，通过前序遍历的结果\[1,2,4,5,3\]和中序遍历的结果\[4,2,5,1,3\]可重建出以下二叉树：

![b270cc4c1390ec4b02577491373d0655.png][]

所以对应的输出为\[1,3,5\]。

### 示例1 ###

输入：

[1,2,4,5,3],[4,2,5,1,3]

返回值：

[1,3,5]

### 题解思路： ###

**在层次遍历基础之上的题目，右视图就是遍历每一层将每一层最后一位元素保存在数组中返回即可。**

import java.util.*;
    
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         * 求二叉树的右视图
         * @param xianxu int整型一维数组 先序遍历
         * @param zhongxu int整型一维数组 中序遍历
         * @return int整型一维数组
         */
        //构建的树的结构
        public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
        }
        //根据中序和前序构建二叉树
        public TreeNode con(int[] xianxu, int[] zhongxu){
            if(xianxu.length==0||zhongxu.length==0){
                 return null;
            }
            TreeNode root=new TreeNode(xianxu[0]);
            for(int i=0;i<zhongxu.length;i++){
                if(root.val==zhongxu[i]){
                    root.left=con(Arrays.copyOfRange(xianxu,1,i+1),Arrays.copyOfRange(zhongxu,0,i));
                    root.right=con(Arrays.copyOfRange(xianxu,i+1,xianxu.length),Arrays.copyOfRange(zhongxu,i+1,zhongxu.length));
                    break;
                }
            }
            return root;
        }
        public int[] solve (int[] xianxu, int[] zhongxu) {
            // write code here
            if(xianxu.length==0||zhongxu.length==0){
                 return null;
            }
            //构建二叉树
            TreeNode root=con(xianxu,zhongxu); 
            
            //层序遍历二叉树，每遍历一层，就把该层的最后一个节点加入list中
            ArrayList<Integer> list=new ArrayList<>();
            Deque<TreeNode> dq=new LinkedList<>();
            dq.offer(root);
            while(!dq.isEmpty()){
                int size=dq.size();
                for(int j=0;j<size;j++){ //遍历该层的所有节点
                    TreeNode temp=dq.poll();
                    if(j==size-1){  //最后一个节点
                        list.add(temp.val);
                    }
                    if(temp.left!=null){
                        dq.offer(temp.left);
                    }
                    if(temp.right!=null){
                        dq.offer(temp.right);
                    }
                    
                }
            } 
            int[] arr=new int[list.size()];  //新建数组
            for(int i=0;i<list.size();i++){  //转移数组
                arr[i]=list.get(i);
            }
            return arr;   
        }
    }

[7698725d6a525c59026575da476f9189.png]: https://img-blog.csdnimg.cn/img_convert/7698725d6a525c59026575da476f9189.png
[21c756ecee5382a5e8f38e68100fd5fd.png]: https://img-blog.csdnimg.cn/img_convert/21c756ecee5382a5e8f38e68100fd5fd.png
[e388429f776c3e849db1e50652139d28.png]: https://img-blog.csdnimg.cn/img_convert/e388429f776c3e849db1e50652139d28.png
[a653a1c4ba59e993029500d6ccca1c05.gif]: https://img-blog.csdnimg.cn/img_convert/a653a1c4ba59e993029500d6ccca1c05.gif
[b270cc4c1390ec4b02577491373d0655.png]: https://img-blog.csdnimg.cn/img_convert/b270cc4c1390ec4b02577491373d0655.png