题目链接

107. Binary Tree Level Order Traversal II

题目描述

题目的意思就是层次遍历二叉树，但是对输出有两个要求：1.按层输出；2.倒序输出每层；

源码

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinaryTreeLevelOrderTraversal107 {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        /**深度遍历使用队列实现**/
        Queue<TreeNode> queue = new LinkedList<>();

        List<List<Integer>> result = new ArrayList<>();


        //判断树是否为空，为空直接返回null
        if(root==null){
            return result;
        }

        int left=1;//表示遍历的当前层还没有遍历的节点
        int nextLevelNodeNum=0;//表示当前层下一层需要遍历的节点

        queue.add(root);

        Stack<List<Integer>> stack = new Stack<>();

        while (!queue.isEmpty()){//遍历二叉树
            List<Integer> eachLevelNodes = new ArrayList<>();

            //根据当前层还剩的节点判断当前层是否全部遍历
            while (left>0){
                TreeNode tempTreeNode = queue.poll();
                eachLevelNodes.add(tempTreeNode.val);
                
                //将当前节点的左右节点加入到队列中，作为下一层需要遍历的节点
                if(tempTreeNode.left!=null){
                    queue.add(tempTreeNode.left);
                    nextLevelNodeNum+=1;
                }
                if(tempTreeNode.right!=null){
                    queue.add(tempTreeNode.right);
                    nextLevelNodeNum+=1;
                }
                
                //当前节点的剩余数减一
                left--;
            }
            //遍历完一层之后，将当前层遍历结果加入到栈中，同时重新开始遍历下一层所以left的值改为即将遍历的下一层的节点数量
            //然后需要统计即将遍历下一层的下一层的节点数，所以将nextLevelNodeNum的值重置为0；
            stack.add(eachLevelNodes);
            left=nextLevelNodeNum;
            nextLevelNodeNum=0;
        }
        
        //将每层的遍历结果弹出栈，然后加入到结果列表中
        while (!stack.isEmpty()){
            result.add(stack.pop());
        }

        return result;
    }
}

其它解法

以下代码摘自讨论区中My DFS and BFS java solution:
DFS solution:

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
        
        if(root == null) return wrapList;
        
        queue.offer(root);
        while(!queue.isEmpty()){
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<Integer>();
            for(int i=0; i<levelNum; i++) {
                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            wrapList.add(0, subList);
        }
        return wrapList;
    }
}

BFS solution:

public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
            levelMaker(wrapList, root, 0);
            return wrapList;
        }
        
        public void levelMaker(List<List<Integer>> list, TreeNode root, int level) {
            if(root == null) return;
            if(level >= list.size()) {
                list.add(0, new LinkedList<Integer>());
            }
            levelMaker(list, root.left, level+1);
            levelMaker(list, root.right, level+1);
            list.get(list.size()-level-1).add(root.val);
        }
    }