Leetcode 107. 二叉树的层序遍历 II

力扣传送门

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

解题思路：

这道题和「102. 二叉树的层序遍历」相似，不同之处在于，第 102 题要求从上到下输出每一层的节点值，而这道题要求从下到上输出每一层的节点值。除了输出顺序不同以外，这两道题的思路是相同的，都可以使用广度优先搜索进行层次遍历。

其实这道题目最关键的一点是能想到用队列，只要这点想到就好办了！

如果要求从上到下输出每一层的节点值，做法是很直观的，在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的尾部。但是这道题要求从下到上输出每一层的节点值，只要对上述操作稍作修改即可：在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部。或者单独使用一个Stack栈对结果进行一个翻转～

代码实现：

方法一：使用栈翻转

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     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;
 *     }
 * }
 */
class Solution {
    Stack<List<Integer>> stack = new Stack(); 
    List<List<Integer>> res = new ArrayList(); 
  
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null){
            return res; 
        }
  
        Queue<TreeNode> queue = new LinkedList(); 
        queue.add(root);
        // 循环直到队列为空
        while(!queue.isEmpty()){ 
            // 获取当前队列的大小（当前层的节点数）
            int size = queue.size(); 
            // 创建一个新的列表用于存储当前层节点的值
            List<Integer> list = new ArrayList(); 
            // 处理当前层的所有节点
            while(size-- > 0){ 
                 // 移除队列中的第一个节点
                TreeNode currNode = queue.poll();
                 // 将当前节点的值添加到列表中
                list.add(currNode.val); 
  
                if(currNode.left != null){
                    // 将当前节点的左子节点加入队列
                    queue.add(currNode.left); 
                }
  
                if(currNode.right != null){
                    // 将当前节点的右子节点加入队列
                    queue.add(currNode.right); 
                }
            }
            // 将节点值的列表压入栈中
            stack.push(list); 
        }
  
        while(!stack.isEmpty()){
            // 从栈中弹出节点值的列表，并添加到结果列表中
            res.add(new ArrayList(stack.pop())); 
        }
        // 返回最终结果（自底向上的层序遍历）
        return res; 
    }
}

方法二：

class Solution {
    // 创建一个链表用于存储最终结果
    List<List<Integer>> res = new LinkedList<List<Integer>>(); 
  
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null){
            // 如果根节点为空，返回空的结果列表
            return res; 
        }
        // 创建一个队列用于进行层序遍历
        Queue<TreeNode> queue = new LinkedList(); 
        // 将根节点加入队列
        queue.add(root); 
        // 循环直到队列为空
        while(!queue.isEmpty()){ 
            // 获取当前队列的大小（当前层的节点数）
            int size = queue.size(); 
            // 创建一个新的列表用于存储当前层节点的值
            List<Integer> list = new ArrayList(); 
            // 处理当前层的所有节点
            while(size-- > 0){ 
                // 移除队列中的第一个节点
                TreeNode currNode = queue.poll(); 
                // 将当前节点的值添加到列表中
                list.add(currNode.val); 
  
                if(currNode.left != null){
                    // 将当前节点的左子节点加入队列
                    queue.add(currNode.left); 
                }
  
                if(currNode.right != null){
                    // 将当前节点的右子节点加入队列
                    queue.add(currNode.right); 
                }
            }
            // 将节点值的列表添加到结果列表的开头（索引为0）
            res.add(0, list); 
        }
        // 返回最终结果（自底向上的层序遍历）
        return res; 
    }
}