Java 数据结构进阶二叉树题集上

目录
  • 1、二叉树的遍历
    • (1)前、中、后序遍历
    • (2)层序遍历
  • 2、获取树中子结点的个数
  • 3、获取二叉树的高度
  • 4、判断是不是完全二叉树
  • 5、判断两个树是否相同
  • 6、另一棵树的子树
  • 7、判断平衡二叉树

二叉树操作的代码大多数使用递归来实现,代码会比较简洁,如果使用非递归,代码会比较的繁荣,而且不易理解。(上)中的题偏向于基础,后面(下)中的题机会比较难。

1、二叉树的遍历

(1)前、中、后序遍历

这里写到的遍历是递归遍历,代码比较简单,后续会写非递归的代码。以前序遍历为例:

如果根节点root为空,直接返回,否则,打印根节点,再分别递归root的左子树和右子树即可。中序遍历的话,先中序遍历左子树,打印根节点,再中序遍历右子树即可。

【代码如下】

//递归实现,比较简单
public void preTree(Node root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preTree(root.left);
        preTree(root.right);
    }

(2)层序遍历

【OJ链接】

OJ的返回值为一个存放链表的链表,所以我们可以将每一层的元素存放在同一个链表中,作为元素存放在要返回的链表中。还是使用队列来遍历链表,每次出根节点,当其左右节点不为空的时候,入左右节点。直到队列为空,遍历完成。

如何判断二叉树每层结点的个数?

在对每层节点出队完成后,队列中剩余结点的个数就是下一层结点的个数。比如:现在给队列如跟节点,队列大小为1,第一层的节点个数就为1;当根节点出对后,我们需要入队根节点的左右节点,如果左节点为null,则只入右节点,此时队列大小为1,第二层的节点个数就为1。

【代码如下】

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

2、获取树中子结点的个数

通常二叉树的问题,都会有两种思路:遍历思路和子问题思路。

如这道题:

我们可以求出它的左子树和右子树中子结点的个数,相加即可;或者,定义计数器,因为要递归,所以我们需要一个全局变量(count),递归左右子树,只要遇到子节点,count就加一。

【代码如下】

//获取叶子节点的个数
    //方法一
    public int getLeafNodeCount1(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
    }
    // 方法二
    public static int count1;
    public void getLeafNodeCount2(Node root){
        if(root==null){
            return ;
        }
        if(root.left==null&&root.right==null){
            count1++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }

3、获取二叉树的高度

获取二叉树的高度,我们只需要获取二叉树左右子树的高度,返回左右子树的最大高度加一即可。

【代码如下】

 // 获取二叉树的高度
    public int getHeight(Node root){
        if(root==null){
            return 0;
        }
        int left=getHeight(root.left);
        int right=getHeight(root.right);
        return left>right?left+1:right+1;
    }

4、判断是不是完全二叉树

【完全二叉树和满二叉树】

  • 满二叉树: 一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树。也就是说,如果一棵二叉树的层数为K,且结点总数是 2^K-1,则它就是满二叉树。
  • 完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

判断完全二叉树,我们可以借助队列来实现,在二叉树不为空的情况下,对二叉树进行层序遍历:定义一个队列,将根节点放入,只要队列不为空,进行出队,将得到的节点的左右节点入队,注意先左后右,节点为空也要进行入队(队列可以存储null)。直到遇到第一个出队的节点为null,对队列中剩下的元素进行遍历,如果全为null,则为完全二叉树;如果存在不为null的结点,则不是完全二叉树。

 public boolean isCompleteTree(Node root){
       Queue<Node> queue=new LinkedList<>();
       queue.offer(root);
       //如果队列为空,会存在空指针异常
       while(!queue.isEmpty()){
           //层序遍历
           Node node=queue.poll();
           if(node!=null){
               //将节点的左右子节点放入队列
               queue.offer(node.left);
               queue.offer(node.right);
           }else{
               //如果node为null,直接对队列进行判断
               break;
           }
       }
       int x=queue.size();
       //判断队列元素是否全为null
       for(int i=0;i<x;++i){
           if(queue.poll()!=null){
               return false;
           }
       }
       return true;
    }

5、判断两个树是否相同

【OJ链接】

存在以下四种情况:

【代码如下】

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

6、另一棵树的子树

【OJ链接】

上面已经给写过判断两棵树是否相等的题,我们只需要判断树p是否等于树q,或者数p的左子树或右子树是否等于树q。分为以下几种情况:

【代码如下】

class Solution {
    //判断两个树是否相等
    public boolean isSameTree(TreeNode root,TreeNode subRoot){
        if(root==null&&subRoot!=null||root!=null&&subRoot==null){
            return false;
        }
        if(root==null&&subRoot==null){
            return true;
        }
        if(root.val!=subRoot.val){
            return false;
        }
        return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right);
    }
    //判断子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null||subRoot==null){
             return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
}

7、判断平衡二叉树

【OJ链接】

高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

首先我们需要写一个函数来求二叉树的高度,只要这个二叉树的左右子树高度差不大于1,且左右子树都是平衡二叉树,则其为平衡二叉树。

【代码如下】

class Solution {
    //求二叉树的高度
    public int maxDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return left>right?left+1:right+1;
    }
    //判断二叉树是不是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1){
            return isBalanced(root.left)&&isBalanced(root.right);
        }
        return false;
    }
}

到此这篇关于Java 数据结构进阶二叉树题集上的文章就介绍到这了,更多相关Java 二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java数据结构之平衡二叉树的实现详解

    目录 定义 结点结构 查找算法 插入算法 LL 型 RR 型 LR 型 RL 型 插入方法 删除算法 概述 实例分析 代码 完整代码 定义 动机:二叉查找树的操作实践复杂度由树高度决定,所以希望控制树高,左右子树尽可能平衡. 平衡二叉树(AVL树):称一棵二叉查找树为高度平衡树,当且仅当或由单一外结点组成,或由两个子树形 Ta 和 Tb 组成,并且满足: |h(Ta) - h(Tb)| <= 1,其中 h(T) 表示树 T 的高度 Ta 和 Tb 都是高度平衡树 即:每个结点的左子树和右子树的高

  • java数据结构之搜索二叉树

    本文实例为大家分享了java数据结构之搜索二叉树的具体代码,供大家参考,具体内容如下 搜索二叉树的定义是:在一个二叉树上,左节点一定比父节点小,右节点一定比父节点大,其他定义跟二叉树相同. 代码实现: public class node {     int data;     public node left, right=null;       public node(int data) {         this.data = data;       }       public node

  • Java数据结构最清晰图解二叉树前 中 后序遍历

    目录 一,前言 二,树 ①概念 ②树的基础概念 三,二叉树 ①概念 ②两种特殊的二叉树 ③二叉树的性质 四,二叉树遍历 ①二叉树的遍历 ②前序遍历 ③中序遍历 ④后序遍历 五,完整代码 一,前言 二叉树是数据结构中重要的一部分,它的前中后序遍历始终贯穿我们学习二叉树的过程,所以掌握二叉树三种遍历是十分重要的.本篇主要是图解+代码Debug分析,概念的部分讲非常少,重中之重是图解和代码Debug分析,我可以保证你看完此篇博客对于二叉树的前中后序遍历有一个新的认识!!废话不多说,让我们学起来吧!!

  • 详解Java数据结构之平衡二叉树

    目录 什么是二叉搜索树 平衡二叉搜索树 平衡二叉搜索树建树程序 计算每个节点的高度 计算每个节点的平衡因子 合并二叉树 旋转调整函数 整体代码 什么是二叉搜索树 简单来说,就是方便搜索的二叉树,是一种具备特定结构的二叉树,即,对于节点n,其左子树的所有节点的值都小于等于其值,其右子树的所有节点的值都大于等于其值.​ 以序列2,4,1,3,5,10,9,8为例,如果以二叉搜索树建树的方式,我们建立出来的逐个步骤应该为 第一步: 第二步: 第三步: 第四步: 第五步: 第六步: 第七步: 第八步:

  • Java 数据结构中二叉树前中后序遍历非递归的具体实现详解

    目录 一.前序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 二.中序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 三.后序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 一.前序遍历 1.题目描述 给你二叉树的根节点 root ,返回它节点值的 前序 遍历. 2.输入输出示例 示例 1: 输入:root = [1,null,2,3] 输出:[1,2,3] 示例2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1

  • 带你了解Java数据结构和算法之二叉树

    目录 1.树 2.二叉树 3.查找节点 4.插入节点 5.遍历树 6.查找最大值和最小值 7.删除节点 ①.删除没有子节点的节点 ②.删除有一个子节点的节点 ③.删除有两个子节点的节点 ④.删除有必要吗? 8.二叉树的效率 9.用数组表示树 10.完整的BinaryTree代码 11.哈夫曼(Huffman)编码 ①.哈夫曼编码 ②.哈夫曼解码 12.总结 1.树 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点通过连接它们的边组成一个

  • Java数据结构二叉树难点解析

    前言 本章,我们主要需要了解以下内容 什么是线索二叉树 怎么去把二叉树线索化 怎么通过线索二叉树查找某个数的后继结点 二叉树的查看--二叉树怎们遍历 什么是线索二叉树 首先我们来了解一下什么是线索二叉树? 定义:一个二叉树通过如下的方法"穿起来":所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继,所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱. 再看一下为什么要有线索二叉树? 顾名思义,线索二叉树,肯定是根据线索查找,查找速度肯定更快. 线索二叉树能线性地遍历二

  • Java数据结构之平衡二叉树的原理与实现

    目录 1 平衡二叉树的概述 2 平衡二叉树的实现原理 2.1 单旋转 2.2 双旋转 2.3 总结 3 平衡二叉树的构建 3.1 类架构 3.2 查找的方法 3.3 检查是否平衡的方法 3.4 插入的方法 3.5 查找最大值和最小值 3.6 删除的方法 4 平衡二叉树的总结 平衡二叉树(AVL树),顾名思义,是一颗很“平衡”的树,它的平衡是相对于排序二叉树来说的.为了避免极端情况下二叉搜索树节点分布不均匀,甚至退化为链表,影响查找效率,我们引入了平衡二叉树,即让树的结构看起来尽量“均匀”,左右子

  • Java 数据结构进阶二叉树题集上

    目录 1.二叉树的遍历 (1)前.中.后序遍历 (2)层序遍历 2.获取树中子结点的个数 3.获取二叉树的高度 4.判断是不是完全二叉树 5.判断两个树是否相同 6.另一棵树的子树 7.判断平衡二叉树 二叉树操作的代码大多数使用递归来实现,代码会比较简洁,如果使用非递归,代码会比较的繁荣,而且不易理解.(上)中的题偏向于基础,后面(下)中的题机会比较难. 1.二叉树的遍历 (1)前.中.后序遍历 这里写到的遍历是递归遍历,代码比较简单,后续会写非递归的代码.以前序遍历为例: 如果根节点root为

  • Java 数据结构进阶二叉树题集下

    目录 1.对称二叉树 2.创建并遍历二叉树 3.二叉树中两节点最近公共祖先 4.二叉搜索树与双向链表 5.根据前序和中序遍历结果创建二叉树 6.二叉树创建字符串 7.非递归实现二叉树前序遍历 8.非递归实现二叉树后序遍历 1.对称二叉树 [OJ链接] 分为以下几种情况: 二叉树为空,是对称二叉树 二叉树不为空,其左子树或者右子树为空,不是对称二叉树 二叉树不为空,左右子树都为空,是对称二叉树 二叉树不为空,左右子树不为空,左右子节点值不同,不是对称二叉树 二叉树不为空,左右子树不为空,左右子节点

  • Java数据结构之并查集的实现

    目录 代码解析 代码应用 实际应用 并查集就是将原本不在一个集合里面的内容合并到一个集合中. 在实际的场景中用处不多. 除了出现在你需要同时去几个集合里面查询,避免出现查询很多次,从而放在一起查询的情况. 下面简单实现一个例子,我们来举例说明一下什么是并查集,以及究竟并查集解决了什么问题. 代码解析 package com.chaojilaji.book.andcheck; public class AndCheckSet { public static Integer getFather(in

  • 详解Java实现数据结构之并查集

    ​一.什么是并查集 对于一种数据结构,肯定是有自己的应用场景和特性,那么并查集是处理什么问题的呢? 并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题,常常在使用中以森林来表示.在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受:即使在空

  • Java数据结构学习之二叉树

    1 背景知识:树(Tree) 在之前的笔记中,我们介绍的链表.栈.队列.数组和字符串都是以线性结构来组织数据的.本篇笔记要介绍的树采用的是树状结构,这是一种非线性的数据组织形式. 树结构由节点和边构成,且不存在环.我们曾在线性表型的数据结构中介绍过循环链表和循环队列,这两种数据结构使得存储容器中的元素形成一个闭环,具体可参看"数据结构学习笔记"系列的相关博文,链接贴在下面: 链表:https://www.jb51.net/article/215278.htm 队列:https://ww

  • java 数据结构并查集详解

    目录 一.概述 二.实现 2.1 Quick Find实现 2.2 Quick Union实现 三.优化 3.1基于size的优化 3.2基于rank优化 3.2.1路径压缩(Path Compression ) 3.2.2路径分裂(Path Spliting) 3.2.3路径减半(Path Halving) 一.概述 并查集:一种树型数据结构,用于解决一些不相交集合的合并及查询问题.例如:有n个村庄,查询2个村庄之间是否有连接的路,连接2个村庄 两大核心: 查找 (Find) : 查找元素所在

  • Java数据结构顺序表从零基础到精通进阶

    目录 一.什么是线性表 二.顺序表 三.手撕顺序表 属性定义 构造方法 接口实现 确保顺序表空间 增加元素 打印顺序表 判断顺序表中是否包含某个元素 查找元素 获取 pos 位置的元素 将 pos 位置的元素值设为 value 删除第一次出现的关键字key 获取顺序表长度 清空顺序表 删除所有的key 一.什么是线性表 线性表是最基本.最简单.也是最常用的一种数据结构.线性表*(linear list)*是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列.常见的线性表有顺序表,链

  • Java进阶之FileUpload完成上传的实例

     Java进阶之FileUpload完成上传的实例 FileUpload是Apache commons下面的一个子项目,用来实现Java项目下的文件上传功能,常见的文件上传还有SmartUpload,Servlet3.0,Struts2. 在这里我用的是commons- fileupload-1.2.1,下面就是一个简单实例,解析过程都写到代码中的注释上了,注释很详细 //创建磁盘文件项工厂 DiskFileItemFactory diskFileItemFactory=new DiskFile

随机推荐