一、二叉树的最小深度
描述:
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例1:
输入: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
思路:
这里的二叉树有两种情况 同时具有左右子树 和 只具有左子树或右子树。
对于 同时具有左右子树的情况 非常简单,可以借鉴上篇文章中我们求最大深度的接口的思路。
我们递归遍历到最后一层,返回较小的高度 + 1。每次遍历分别计算左右子树的高度,防止多次递归调用。
如果遇到 NULL 则返回0。
对于 只有单边子树 的情况就比较麻烦了,由于没有一边的子树,我们肯定是返回有子树的一边的高度。
但是如果套用 同时具有左右子树的情况 就不行了,到时候本来应该返回有子树的那一边,但是返回的总是1。
所以需要 两种情况分别处理 :
首先求出左右子树高度和 左右子树中的最小高度。
如果 当前树有左右子树 则返回最小高度 + 1;
如果 当前树的左右子树为空 那么就返回 左边高度 + 右边高度 + 1,因为 有一边的高度必定为0,所以加上的高度并不影响正确结果。
二、单值二叉树
链接:965. 单值二叉树
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true
;否则返回 false
。
示例1:
输入:[1,1,1,1,1,null,1] 输出:true
示例 2:
输入:[2,2,2,5,2] 输出:false
提示:
给定树的节点数范围是 [1, 100]。
每个节点的值都是整数,范围为 [0, 99] 。
思路:
单值树就是每个节点的值都相同。
而一棵树是单值树,那么它的 根节点的值和左右子树的值一定相同,那么就可以拆分成子问题。
接下来判断各种情况:
如果 节点为空 ,那么是单值二叉树,返回真;
如果 左子树不为空且值 和 根节点值不相等 ,返回假;
如果 右子树不为空且值 和 根节点值不相等, 返回假;
就这样分别递归左右子树,即可判断是否为单值二叉树。
三、相同的树
链接:100. 相同的树
描述:
给你两棵二叉树的根节点 p
和 q
,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3] 输出:true
示例2:
输入:p = [1,2], q = [1,null,2] 输出:false
示例3:
提示:
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104
思路:
判断两棵树是否相等,我们先思考一下如何才算相等:
对于 两棵空树 ,必定相等,返回真;
如果 一棵树空,另一棵树不为空 ,那么不相等,返回假;
如果 树中值相同但是结构不同 ,那么也不相等,返回假;
如果 两棵树对应节点的值不相等,那么也不相等,返回假;
那么只要分别递归两棵的左右子树,如果一直递归到底都是真,且左右子树返回的结果都为真,那么这两棵树就相同。