您现在的位置是:首页 > 正文

剑指offer——二叉树层序遍历及其相关延伸面试算法题

2024-02-29 14:06:43阅读 2

目录

从上到下打印二叉树II

题目解析

二叉树的右视图

题目解析

二叉树左视图


从上到下打印二叉树II

从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果:

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

题目解析

        这题的主要意思是按照二叉树的层序遍历输出结果,因此使用 queue 这一数据结构,每次将同一深度的节点放入队列中。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//首先将根节点放入
        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {//每次queue的大小是可变的
                TreeNode tmp = queue.poll();
                
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
                list.add(tmp.val);
            }
            ans.add(list);
        }
        return ans;
    }
}

二叉树的右视图

给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:

输入: [1,null,3]
输出: [1,3]
示例 3:

输入: []
输出: []

题目解析

        这一题是二叉树层序遍历的变种,是在二叉树层序遍历的同时,若遇到此层最后一个节点,那么把它放入结果集中。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            
            for(int i = 0; i < size; i++) {
                TreeNode tmp = queue.poll();
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                    
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                    
                }
                if(i == size - 1) {//判断是否是此层最后一个节点
                    ans.add(tmp.val);
                }
                
            }

        }
        return ans;
    }
}

二叉树左视图

        和右视图一样的原理,只是在判断时条件变为是否是此层第一个元素。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            
            for(int i = 0; i < size; i++) {
                TreeNode tmp = queue.poll();
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                    
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                    
                }
                if(i == 0) {
                    ans.add(tmp.val);
                }
                
            }

        }
        return ans;
    }
}

网站文章

  • hadoop2.7完全分布式搭建

    hadoop2.7完全分布式搭建

    环境准备 一共四台服务器,均为centos7, 安装jdk8 服务1 :192.168.1.38 服务2 :192.168.1.39 服务3 :192.168.1.40 服务4 : 192.168.1.41 1 修改主机名 为 s201 vi /etc/hostname 2 修改host文件 vi /etc/host 127.0.0.1 localhost 192.168.1.38 s20...

    2024-02-29 14:06:18
  • Angular中响应式表单 FormBuilder、FormControl 、FormGroup、FormArray、setControl、setValue用法总结

    以我的项目作为示例,总结一下Angular响应式表单的应用和常用的方法: 1.创建表单 form.ts代码 import { Component, OnInit } from &quot;@angul...

    2024-02-29 14:06:11
  • 如何优雅的处理前端异常(前端高阶必备)

    如何优雅的处理前端异常(前端高阶必备)

    (内容同步自小邹的头条号:沪漂程序员的生活史)前端一直是距离用户最近的一层,随着产品的日益完善,我们会更加注重用户体验,而前端异常却如鲠在喉,甚是烦人。如何更好的处理前端异常有助于我们问题的排查和代码的规范化。 一、为什么要处理异常?异常是不可控的,会影响最终的呈现结果,但是我们有充分的理由去做这样的事情。增强用户体验; 远程定位问题; 未雨绸缪,及早发现问题; 无法...

    2024-02-29 14:06:00
  • qsort函数:可排序任何类型元素的函数

    qsort函数:可排序任何类型元素的函数

    函数简介调用时需要库函数<stdlib.h>void qsort (void* base, size_t num, size_t size, int (*compar)(cons...

    2024-02-29 14:05:31
  • 【生活工作经验 八】掌握大局,MBA考前调研

    【生活工作经验 八】掌握大局,MBA考前调研

    最近在给自己制定职业生涯规划,并且结合公司的职级职等制度,想要走M路线,而MBA无疑是一个重要的资本,好处有如下几种: 拓展视野和思维,跳出当前的局限,接受系统的管理者培养体系 拓展人脉,结识各行各业...

    2024-02-29 14:05:21
  • opencv_python使用cv2.imread()读取中文路径报错问题 热门推荐

    opencv_python使用cv2.imread()读取中文路径报错:window.cpp:325: error: (-215) size.width&gt;0 &amp;&amp; size.height&gt;0 in function cv::imshow,解决办法为......

    2024-02-29 14:05:13
  • Pytorch分布式报错1.non-zero exit status,2.cuDNN error:CUDNN_STATUS_INTERNAL_,3.CUDA error:illegal memory

    1.returned non-zero exit status 1. One epoch之后报错,信息如下: RuntimeError: Expected to have finished reduc...

    2024-02-29 14:04:45
  • 【转载】JDK集合源码解析

    1、转载至:Vector、Stack、ArrayList、LinkedList、HashMap源码解析Vector:继承了AbstractList抽象类,实现了List接口,实现了RandomAcce...

    2024-02-29 14:04:36
  • lucene简单应用

    lucene简单应用

    本文只涉及lucene的应用,关于其原理等暂不涉及,有时间再单独写一篇。用常用的文章类作为例子,实体类代码如下:@Datapublic class Article implements Serializable{ private Long id; private String title; private String describe; priva

    2024-02-29 14:04:25
  • create-react-app创建react项目使用less的修改过程。

    在使用create-react-app创建react项目的时候,原始的项目结构是不能够使用less预编译器。使用 yarn reject暴露配置文件$ yarn reject$ react-scripts ejectNOTE: Create React App 2 supports TypeScript, Sass, CSS Modules and more without eje...

    2024-02-29 14:04:18