腾讯云开发者社区-腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

大闲人柴毛毛

专栏作者

189

文章

253222

阅读量

63

订阅数

剑指 offer代码解析——面试题39二叉树的深度

题目：输入一颗二叉树的根结点，求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径，最长路径的长度为树的深度。分析：本题是一道典型的“分治法”。要求一棵二叉树的高度，我们可以将问题分解，先分别求左右子树的高度，然后取较大值加一即为整棵二叉树的高度。接下来按照这种思路继续求左右子树的高度，直到子树为叶子结点时，此时树(即叶子结点)的高度为1。 /** * 题目：输入一颗二叉树的根结点，求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径，最长路径的长度为树的深度。 * @author

大闲人柴毛毛

2018-03-09

7620

剑指 offer代码解析——面试题39判断平衡二叉树(高效方法)

题目：输入一颗二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的高度相差不超过1，那么它就是一棵平衡二叉树。分析：所谓平衡二叉树就是要确保每个结点的左子树与右子树的高度差在－1到1之间。由于之前一题已经给出了二叉树高度的计算方法，因此本题最直观的思路就是分别计算每个结点的左子树高和右子树高，从而判断一棵树的所有结点是否均为平衡二叉树。上一篇博客中采用了一种较为常规的思路，但由于涉及到重复计算子树的高度，因此性能并不好，接下来提出一种从下而上，依次判断每个子树是否为

大闲人柴毛毛

2018-03-09

1.1K0

剑指offer代码解析——面试题19二叉树的镜像

分析：所谓“镜像”就是从镜子里看到的样子。我们可以画一棵二叉树，然后画出该二叉树的镜像。画完图之后我们会发现，所谓“二叉树的镜像”就是把二叉树中所有子树的左孩子和右孩子进行交换。因此需要遍历二叉树所有的结点，在遍历的同时交换非叶子结点的左右子树。遍历我们可以使用先序遍历，首先判断当前根结点是否为叶子结点，若非叶子结点，则交换左右孩子，然后再分别对左右孩子进行相同的操作。首先，我们需要构造二叉树的结点类，一个结点中包含一个数据域data、一个左孩子left、一个右孩子right，代码如下：

大闲人柴毛毛

2018-03-09

6710

剑指offer代码解析——面试题23从上往下打印二叉树

本题的详细分析过程均在代码注释中： import java.util.Queue; import java.util.concurrent.LinkedBlockingQueue; /** * 题目：从上到下打印二叉树的结点，同一层的结点按照从左到右的顺序打印。 * @author 大闲人柴毛毛 * @date 2016年3月15日 */ public class PrintBinaryTree { /** * 分析：学过数据结构便可知，本题实则为宽度优先遍历二叉树。 * 在数据结构中，

大闲人柴毛毛

2018-03-09

5920

剑指offer代码解析——面试题24二叉搜索树的后序遍历序列

本题有bug，欢迎大神指教！ /** * 题目：输入一个整数数组，判断该数组书不是某二叉搜索数的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意两个数字都互不重复。 * @author 大闲人柴毛毛 * @date 2016年3月15日 */ public class SearchTree { /** * 分析：看过题目后本题最直观的思路就是通过后序遍历序列还原这棵二叉树，然后判断该二叉树是否为二叉搜索树。 * 然而学过数据结构就会知道，如果给一棵二叉树的中序遍

大闲人柴毛毛

2018-03-09

6410

剑指offer代码解析——面试题25二叉树中和为某一值的路径

题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。PS：从根结点开始，一直到叶子结点形式一条路径。分析：要找出路径之和为指定整数的路径，就需要遍历二叉树的所有路径。此外，由于路径是指根结点到叶子结点的线段，因此我们想到采用深度优先的方式遍历二叉树。深度优先算法又分为：先序遍历、中序遍历、后序遍历，其中先序遍历符合我们的要求。首先需要创建一个栈，用来保存当前路径的结点。采用先序遍历算法遍历结点时，先将途中经过的结点均存入栈中，然后判断当前结点是否为叶子结点，若不是叶子结点

大闲人柴毛毛

2018-03-09

5970

没有更多了

社区活动

RAG七天入门训练营

鹅厂大牛手把手带你上手实战

Python精品学习库

代码在线跑，知识轻松学

博客搬家 | 分享价值百万资源包

自行/邀约他人一键搬运博客，速成社区影响力并领取好礼

技术创作特训营·精选知识专栏

往期视频·千货材料·成员作品最新动态