107. 二叉树的层次遍历 II

傷城~ 2023-02-18 08:04 105阅读 0赞

# 题目来源 #

[107. 二叉树的层次遍历 II][107. _ II]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 队列 ##

class Solution {
        
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
        
            LinkedList<List<Integer>> lists = new LinkedList<>();
            if (root == null){
        
                return lists;
            }
    
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
        
                List<Integer> list = new ArrayList<>();
                // 每次都取出一层的所有数据
                int size = queue.size();
                for (int i = 0; i < size; i++){
        
                    TreeNode pop = queue.pop();
                    list.add(pop.val);
                    if (pop.left != null){
        
                        queue.offer(pop.left);
                    }
    
                    if (pop.right != null){
        
                        queue.offer(pop.right);
                    }
    
                }
                // 每次都往队头塞
                lists.addFirst(list);
            }
    
            return lists;
        }
    }

![在这里插入图片描述][20200616144121822.png]

## 递归 ##

由于递归的特性，会优先处理下面的节点，因此会穿越不同的层。所以当要加入某个节点时，我们必须直到当前节点的深度，

[107. _ II]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616145821670.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200616144121822.png]: https://img-blog.csdnimg.cn/20200616144121822.png