题目地址(107. 二叉树的层序遍历 II)

https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

题目描述

  1. 给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
  3. 例如：
  4. 给定二叉树 [3,9,20,null,null,15,7],
  6.     3
  7.    / \
  8.   9  20
  9.     /  \
  10.    15   7
  13. 返回其自底向上的层序遍历为：
  15. [
  16.   [15,7],
  17.   [9,20],
  18.   [3]
  19. ]

前置知识


公司

  • 暂无

思路

本质就是把层序遍历的顺序改变 返回的list可以使用linkedlist使用队列的方式来存储 将数据放到列表的头部

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.     public List<List<Integer>> levelOrderBottom(TreeNode root) {
  19.      LinkedList<List<Integer>> res = new LinkedList<>();
  20.             //使用队列来存储层序遍历的节点
  21.             Queue<TreeNode> queue = new LinkedList<>();
  22.             if(root==null){
  23.                 return res;
  24.             }
  25.             queue.offer(root);
  26.             while (!queue.isEmpty()) {
  27.                 ArrayList<Integer> temp = new ArrayList<>();
  28.                 //每次循环的时候size都不一样大小 1 -> 2 -> 4 大概这样的
  29.                 int len = queue.size();
  30.                 //循环当前层的节点数量
  31.                 while (len > 0) {
  32.                     //弹出最先进去的节点 并放到队列中
  33.                     TreeNode poll = queue.poll();
  34.                     temp.add(poll.val);
  35.                     //将节点的左右节点放入队列(如果有)
  36.                     if (poll.left != null) {
  37.                         queue.offer(poll.left);
  38.                     }
  39.                     if (poll.right != null) {
  40.                         queue.offer(poll.right);
  41.                     }
  42.                     len--;
  43.                 }
  44.                 res.addFirst(temp);
  45.             }
  46.             return res;
  47.     }
  48. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：107. 二叉树的层序遍历 II - 图1#card=math&code=O%28n%29&id=VsuwQ)
  • 空间复杂度：107. 二叉树的层序遍历 II - 图2#card=math&code=O%28n%29&id=VMYGl)