剑指offer计划6( 搜索与回溯算法简单版)java

作者: 程序员khaos

1.1、题目1

剑指 Offer 32 - I. 从上到下打印二叉树 {剑指-offer-32—i-从上到下打印二叉树}

1.2、解法

其实这三道题都是广度遍历二叉树的方式。

通过队列实现,存进数组中返回。

1.3、代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) 
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>()};
        ArrayList<Integer> array = new ArrayList<Integer>();
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            array.add(node.val);
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
        }

        int[]res= new int[array.size()];
        for(int i=0;i<array.size();i++){
            res[i]=array.get(i);
        }
        return res;

    }
}

2.1、题目2

剑指 Offer 32 - II. 从上到下打印二叉树 II {剑指-offer-32—ii-从上到下打印二叉树-ii}

2.2、解法

这题改了改,数组需要分层次,就在while里定义一个List,到后面存进大的List中返回即可。这题答案是直接copy的~~

2.3、代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) 
 * }
 */


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

3.1、题目3

剑指 Offer 32 - III. 从上到下打印二叉树 III {剑指-offer-32—iii-从上到下打印二叉树-iii}

3.2、解法

这题是通过两端添加,其实就是上题的稍微修改版本。这题答案是直接copy的~~

3.3、代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部
                else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

原文创作:程序员khaos

原文链接:https://www.cnblogs.com/urmkhaos/p/15234316.html

更多推荐

更多
  • Go编程秘籍-三、数据转换与组合 本章将展示一些在数据类型之间转换、使用非常大的数字、使用货币、使用不同类型的编码和解码(包括 Base64 和gob)以及使用闭包创建自定义集合的示例。转换数据类型和接口转换,使用 math 和 math/big ...
  • Go编程秘籍-一、I/O 和文件系统 Go 为基本和复杂 I/O 提供了极好的支持。本章中的方法将探索用于处理 I/O 的常见 Go 接口,并向您展示如何使用它们。Go 标准库经常使用这些接口,本书中的食谱都将使用这些接口。本章将介绍以下配方:使用公共 I/O ...
  • Go编程秘籍-二、命令行工具 命令行应用是处理用户输入和输出的最简单方法之一。本章将重点介绍基于命令行的交互,如命令行参数、配置和环境变量。最后,我们将介绍一个在 Unix 和 Bash for Windows 中为文本输出着色的库。
  • Go编程秘籍-零、前言 要使用本书,您需要以下内容:Unix 编程环境。Go 1.x 系列的最新版本。互联网连接。如各章所述,允许安装其他软件包。各章节的技术要求部分中提到了各配方的先决条件和其他安装要求。
  • Go编程秘籍-十一、分布式系统 本章将探讨管理分布式数据、编排、容器化、度量和监视的方法。这些将成为编写和维护微服务和大型分布式应用工具箱的一部分。在本章中,我们将介绍以下配方:与 concur 一起使用服务发现,利用 Raft 实现基本共识,与 Docker ...
  • Go编程秘籍-十、并行与并发 Go 提供了使并行应用成为可能的原语。Goroutines 允许任何函数变成异步和并发的。通道允许应用设置与 Goroutines 的通信。在本章中,我们将介绍以下配方:使用通道和 select 语句,使用 sync.WaitGroup ...
  • Go编程秘籍-十二、反应式编程和数据流 本章还将探讨与卡夫卡联系的各种方式,并使用它来处理信息。最后,本章将演示如何在 Go 中创建一个基本的graphql服务器。在本章中,我们将介绍以下配方:使用 Goflow 进行数据流编程,与 Kafka 一起使用异步生产者,将卡夫卡连接到...
  • Go编程秘籍-九、测试 Go 代码 本章将分享一些测试 Go 代码的方法。在本章中,我们将介绍以下配方:使用标准库进行模拟,使用 Mockgen 包模拟接口,使用表驱动测试提高覆盖率,使用第三方测试工具,使用 Go 进行行为测试,在 Go ...
  • Go编程秘籍-十三、无服务器编程 本章将重点介绍无服务器架构,并将其与 Go 语言结合使用。无服务器架构是开发人员不管理后端服务器的架构。这包括亚马逊 Lambda、谷歌应用引擎和 Firebase 等服务。这些服务允许您在 web 上快速部署应用和存储数据。Apex ...
  • Go编程秘籍-五、网络编程 Go 标准库为网络操作提供了大量支持。它包括允许您使用 HTTP 管理 TCP/IP、UDP、DNS、邮件和 RPC 的包。包括gorilla/websockets,用于可在正常 HTTP 处理程序中使用的 WebSocket ...
  • 近期文章

    更多
    文章目录

      推荐作者

      更多