(Java）leetcode-107 Binary Tree Level Order Traversal II（二叉树的层次遍历 II ）

快来打我* 2023-02-16 09:27 4阅读 0赞

# 题目描述 #

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70]

# 思路 #

层次遍历，可以直接套BFS框架：

Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()) { 
                int size = queue.size();
    
                for (int i = 0; i < size; i++) { 
                    TreeNode current = queue.poll();
                    if (current.left != null) queue.offer(current.left);
                    if (current.right != null) queue.offer(current.right);                
                }
            }

需要注意的就是结果与从上往下的顺序相反，需要对正向结果做一次倒置，那么用栈就可以实现啦。

## 代码 ##

class Solution { 
        public List<List<Integer>> levelOrderBottom(TreeNode root) { 
        	List<List<Integer>> resultList = new ArrayList<>();
        	if (root == null) return resultList;
    
        	Stack<List<Integer>> stack = new Stack<>();
            Queue<TreeNode> queue = new LinkedList<>();
    
            queue.offer(root);
            while(!queue.isEmpty()) { 
                int size = queue.size();
                List<Integer> levelList = new ArrayList<>();
                for (int i = 0; i < size; i++) { 
                    TreeNode current = queue.poll();
                    levelList.add(current.val);
                    if (current.left != null) queue.offer(current.left);
                    if (current.right != null) queue.offer(current.right);                
                }
                stack.push(levelList);
            }       
            while(!stack.empty()) resultList.add(stack.pop());
            return resultList;
        }
    }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200609153102737.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200609153251280.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk=,size_16,color_FFFFFF,t_70