算法面试真题详解:二叉树的层次遍历 II-阿里云开发者社区

开发者社区> 算法编程> 正文

算法面试真题详解:二叉树的层次遍历 II

简介: 算法面试真题详解:二叉树的层次遍历 II

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

在线评测地址:领扣题库官网
例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;
   }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接