【数据结构】二叉树OJ练习

简介: 【数据结构】二叉树OJ练习

一、二叉树的最小深度


链接111. 二叉树的最小深度


描述


给定一个二叉树,找出其最小深度。


最小深度是从根节点到最近叶子节点的最短路径上的节点数量。


说明:叶子节点是指没有子节点的节点。


示例1

b369d72262ac946d3a9dbc5b1520f90f.jpeg

输入:root = [3,9,20,null,null,15,7]
输出:2


示例2

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5



提示:

  • 树中节点数的范围在 [0, 105]
  • -1000 <= Node.val <= 1000

思路

这里的二叉树有两种情况 同时具有左右子树只具有左子树或右子树

1b07416d8593613b703ac2f4f7f1f9d7.png


对于 同时具有左右子树的情况 非常简单,可以借鉴上篇文章中我们求最大深度的接口的思路。

我们递归遍历到最后一层,返回较小的高度 + 1。每次遍历分别计算左右子树的高度,防止多次递归调用。


如果遇到 NULL 则返回0。


对于 只有单边子树 的情况就比较麻烦了,由于没有一边的子树,我们肯定是返回有子树的一边的高度。

但是如果套用 同时具有左右子树的情况 就不行了,到时候本来应该返回有子树的那一边,但是返回的总是1。


所以需要 两种情况分别处理 :


   首先求出左右子树高度和 左右子树中的最小高度。


   如果 当前树有左右子树 则返回最小高度 + 1;


   如果 当前树的左右子树为空 那么就返回 左边高度 + 右边高度 + 1,因为 有一边的高度必定为0,所以加上的高度并不影响正确结果。


4acb8f149b5f6e688b4114031a1765e1.png



二、单值二叉树


链接965. 单值二叉树


如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。


只有给定的树是单值二叉树时,才返回 true;否则返回 false


示例1

screen-shot-2018-12-25-at-50104-pm.png

输入:[1,1,1,1,1,null,1]
输出:true

示例 2:

screen-shot-2018-12-25-at-50050-pm.png


输入:[2,2,2,5,2]
输出:false


提示:

   给定树的节点数范围是 [1, 100]。

   每个节点的值都是整数,范围为 [0, 99] 。


思路:


单值树就是每个节点的值都相同。


而一棵树是单值树,那么它的 根节点的值和左右子树的值一定相同,那么就可以拆分成子问题。

接下来判断各种情况:


   如果 节点为空 ,那么是单值二叉树,返回真;

   如果 左子树不为空且值 和 根节点值不相等 ,返回假;

   如果 右子树不为空且值 和 根节点值不相等, 返回假;


就这样分别递归左右子树,即可判断是否为单值二叉树。


a49a36bf56a02a51a53592bd71085fb2.png



三、相同的树


链接100. 相同的树


描述

给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。


示例 1

2a27669123cf48ac4ba9803a33825919.jpeg

输入:p = [1,2,3], q = [1,2,3]
输出:true


示例2

e020eba7742fa7e58b8ed716c16f4374.jpeg

输入:p = [1,2], q = [1,null,2]
输出:false


示例3

ee4fb2e327ede5f03eb8e9f4ec08e0b8.jpeg


提示:

   两棵树上的节点数目都在范围 [0, 100] 内

   -104 <= Node.val <= 104


思路:


判断两棵树是否相等,我们先思考一下如何才算相等:


   对于 两棵空树 ,必定相等,返回真;

   如果 一棵树空,另一棵树不为空 ,那么不相等,返回假;

   如果 树中值相同但是结构不同 ,那么也不相等,返回假;

   如果 两棵树对应节点的值不相等,那么也不相等,返回假;


那么只要分别递归两棵的左右子树,如果一直递归到底都是真,且左右子树返回的结果都为真,那么这两棵树就相同。


4ba7d58b51d3ebe5d4364722e36f0381.png




相关文章
|
16天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
65 8
|
1月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
20 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
1月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
23 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
1月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
27 1
|
1月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
24 1
|
1月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
1月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
24 0
|
17天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
91 9
|
8天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
16 1