层序遍历oj

超、凢脫俗 2023-10-02 13:44 10阅读 0赞

题目内容：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

解题思路：

>  *  **和层序遍历基本一样，只不过是输出由二维数组形式接收了**
>  *  **先考虑使用队列，它的特性是先进先出，让二叉树的根节点先入队列**
>  *  **在大循环当中，只需每次将便利的结点的左右子树，若不为空，就让他们入队列**
>  *  **在for循环当当中，进行一层结点的遍历，临界点条件就是用队列的有效元素的个数，当上一层遍历完的时候，这一层所有节点的子节点都已经入队列，所以，下次循环遍历时的个数，就刚好等于一层结点的个数**

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
    
            //判断二叉树是否为空，如果为空，返回null
            if(root == null){
                return list;
            }
    
            //使用队列的特性，先入先出,并且先让根节点入队列
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
    
            while(!q.isEmpty()){
    
                int count = q.size();
                List<Integer> value = new ArrayList<>();
                for(int i = 0;i < count;i++){
                    TreeNode cur = q.poll();
                    value.add(cur.val);
                    
                    //如果左子树不为空，就让他入队列
                    if(cur.left != null){
                        q.offer(cur.left);
                    }
                        
                    if(cur.right != null){
                        q.offer(cur.right);
                    }
                }
                list.add(value);
            }
    
            return list;
        }
    }

变形形式：返回结果和上面有所不同，需要逆序

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

方法一：使用数组的下标进行操作，交换两个下标所在位置，数组元素的值

方法二：使用栈的特性，后进先出，就可以解决

class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
    
            if(root == null){
                return list;
            }
            
            Stack<List<Integer>> s = new Stack<>();
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
    
            while(!q.isEmpty()){
    
                List<Integer> value = new ArrayList<>();
                int count = q.size();
                for(int i = 0;i < count;i++){
                    TreeNode cur = q.poll();
                    value.add(cur.val);
    
                    if(cur.left != null){
                        q.offer(cur.left);
                    }
    
                    if(cur.right != null){
                        q.offer(cur.right);
                    }
                }
    
                s.push(value);
            }
    
            while(!s.empty()){
                list.add(s.pop());
            }
    
            return list;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6b0d967c7ab249e59f99953ae8c1efd3.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/120137b8f2484cb4b441527b23c889af.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16