[leetcode-二叉树层次遍历并统计每层节点数]--107. Binary Tree Level Order Traversal II

àì夳堔傛蜴生んèń 2022-07-12 03:40 141阅读 0赞

Question 107. Binary Tree Level Order Traversal II

> Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
> 
> For example:  
> Given binary tree \[3,9,20,null,null,15,7\],

3
       / \   9  20
        /  \    15   7

return its bottom-up level order traversal as:

[
      [15,7],
      [9,20],
      [3]
    ]

> 中文：二叉树层次遍历并统计每层结点。这里和102题的区别在于，这里每层的输出是倒序的，也就是从最后一层向上输出直到根节点。

这一题和102解决思路差不多，不过这里使用大了stack来存储每层结点的list达到目的。

/** * 二叉树的层次遍历 * 使用队列实现 * @param root * @return */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();//队列里面存放结点
        List<List<Integer>> result = new ArrayList<List<Integer>>();
    
        Stack<List<Integer>> temp = new Stack<List<Integer>>();
    
        //如果为空树就直接返回
        if(root == null){
            return result;
        }
    
        queue.offer(root);//根节点先入队
        //只要队列非空就一直循环;
        while (!queue.isEmpty()){
            int levelNum = queue.size();//获取当前层的节点数.
            List<Integer> subList = new ArrayList<>();
            //遍历当前层结点
            for(int i=0; i<levelNum; i++){
                //队首出队并将value加入子list
                TreeNode node = queue.poll();
                subList.add(node.val);
    
                //将非空左右子树加入queue
                if(node.left != null){
       //如果队首的左结点不为空就把左结点入队
                    queue.offer(node.left);
                }
                if(node.right != null){
       //如果队首的右结点不为空就把右结点入队
                    queue.offer(node.right);
                }
            }
            temp.push(subList);//入栈
        }
    
        while(!temp.isEmpty()){
            result.add(temp.pop());
        }
    
        return result;
    }

测试类

public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
    
        List<List<Integer>> res = Question107.levelOrder(root);
    
        for(List<Integer> is : res){
            for(Integer i : is){
                System.out.print(i + ", ");
            }
    
            System.out.println();
        }
    }

输出：

15, 7, 
    9, 20, 
    3,

本文完整代码github：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question107.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question107.java]

[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question107.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question107.java