欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Google 面试题:二叉树的层次遍历 II

程序员文章站 2022-04-29 17:30:49
给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)在线评测地址:LintCode 领扣例1:输入:{1,2,3}输出:[[2,3],[1]]解释: 1 / \ 2 3它将被序列化为 {1,2,3}层次遍历 例2:输入:{3,9,20,#,#,15,7}输出:[[15,7],[9,20],[3]]解释: ......

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)

在线评测地址:LintCode 领扣

例1:

输入:
{1,2,3}
输出:
[[2,3],[1]]
解释:
 1
   / \
 2 3
它将被序列化为 {1,2,3}
层次遍历 

例2:

输入:
{3,9,20,#,#,15,7}
输出:
[[15,7],[9,20],[3]]
解释:
    3
   / \
  9  20
    /  \
   15   7
它将被序列化为 {3,9,20,#,#,15,7}
层次遍历 

算法:二叉树的层次遍历

层次遍历,可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历,开辟一个新队列,让头结点入队并计算此时的长度,每次都将一层的所有节点压入队列后,得到队列的大小,然后将这这一层的所有点都进行遍历,将从左到右每一个点的子节点都压入队列,将本层节点遍历完后,继续下一层的遍历,然后开始循环,一直遍历到底层,判断的终止条件就是队列为空。

  • 循环里面,队列头出队,判断其是否有左右子结点,如果有,则入队,但此时还不需要更新队列的长度,当前队列的长度是每层的长度。当这层的长度减为0时,就说明这层的遍历结束,开始更新长度为下一层的长度。
  • 出队的元素的值按照一层层压入结果数组
  • 因为题目要求自底向上,那么我们不移动每一层的内容,对层进行倒序

复杂度分析

  • 时间复杂度​O(n)​
    • n为树的节点数
  • 空间复杂度​O(n)​
    • 保存节点位置 n为树的节点数
public class Solution {
   /**
    * @param root: A tree
    * @return: buttom-up level order a list of lists of integer
    */
   public List<List<Integer>> levelOrderBottom(TreeNode root) {
      // write your code here
      List<List<Integer>> ans = new ArrayList<>();
      LinkedList<TreeNode> queue = new LinkedList<>();
      if (root != null) {
         queue.offer(root);
      }
      //层次遍历
      while (!queue.isEmpty()) {
         int len = queue.size();
         List<Integer> tmpList = new ArrayList<>();
         while (len > 0) {
            TreeNode treeNode = queue.poll();
            tmpList.add(treeNode.val);
            if (treeNode.left != null) { //左子树不为空的话压入队列
               queue.offer(treeNode.left);
            }
            if (treeNode.right != null) {//右子树不为空的话压入队列
               queue.offer(treeNode.right);
            }
            len--;
         }
         ans.add(tmpList);//储存当前层的节点
      }
      //倒序
      Collections.reverse(ans);
      return ans;
   }
}

更多题解参考:九章算法

本文地址:https://blog.csdn.net/JiuZhang_ninechapter/article/details/110182369