一、题目 请实现一个函数来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。 二、解题思路 通常我们有三种不同的二叉树遍历算法,即前序遍历、中序遍历和后序遍历。在这三种遍历算法中,都是先遍历左子结点再遍历右子结点。我们是否可以定义一种遍历算法,先遍历右子结点再遍历左子结点?比如我们针对前序遍历定义一种对称的遍历算法,即先遍历父节点,再遍历它的右子结点,最后遍历它的左子结点。
一、题目 给定一棵二叉树和其中的一个结点,如何找出中序遍历顺序的下一个结点?树中的结点除了有两个分别指向左右子结点的指针以外,还有一个指向父节点的指针。 二、解题思路 如果一个结点有右子树,那么它的下一个结点就是它的右子树中的左子结点。也就是说右子结点出发一直沿着指向左子结点的指针,我们就能找到它的下一个结点。 接着我们分析一个结点没有右子树的情形。如果结点是它父节点的左子结点,那么它的下一个结点
一、题目 求树中两个结点的最低公共祖先,此树不是二叉树,并且没有指向父节点的指针。 二、解题思路 我们首先得到一条从根结点到树中某一结点的路径,这就要求在遍历的时候,有一个辅助内存来保存路径. 比如我们用前序遍历的方法来得到从根结点到H 的路径的过程是这样的:( 1 )遍历到A,把A 存放到路径中去,路径中只有一个结点A; ( 2 )遍历到B,把B 存到路径中去,此时路径为A->B; ( 3 )遍
一、题目 输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1 ,那么它就是一棵平衡二叉树。 二、解题思路 解法一:需要重蟹遍历结点多次的解法 在遍历树的每个结点的时候,调用函数treeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1 ,按照定义它就是一棵平衡的二叉树。 解法二:每个结点只遍历一次的解法 用后序遍历的方式遍
一、题目 输入一棵二叉树的根结点,求该树的深度。从根结点到叶子点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 二、解题思路 如果一棵树只有一个结点,它的深度为1。 如果根结点只有左子树而没有右子树, 那么树的深度应该是其左子树的深度加1,同样如果根结点只有右子树而没有左子树,那么树的深度应该是其右子树的深度加1. 如果既有右子树又有左子树, 那该树的深度就是其左、右子
一、题目 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 二、解题思路 在二叉树中,每个结点都有两个指向子结点的指针。在双向链表中,每个结点也有两个指针,它们分别指向前一个结点和后一个结点。由于这两种结点的结构相似,同时二叉搜索树也是一种排序的数据结构,因此在理论上有可能实现二叉搜索树和排序的双向链表的转换。 在搜索二叉树中,左子
一、题目 输入一棵二叉树和一个整数, 打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 二、解题思路 由于路径是从根结点出发到叶结点, 也就是说路径总是以根结点为起始点,因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中,只有前序遍历是首先访问根结点的。 当用前序遍历的方式访问到某一结点时, 我们把该结点添加到路径上,并累加该结
一、题目 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。 二、解题思路 在后序遍历得到的序列中, 最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分: 第一部分是左子树结点的值,它们都比根结点的值小: 第二部分是右子树结点的值,它们都比根结点的值大。 三、解题代码 public class
一、题目 从上往下打印出二叉树的每个结点,同一层的结点按照从左向右的顺序打印。 二、解题思路 这道题实质是考查树的遍历算法。从上到下打印二叉树的规律:每一次打印一个结点的时候,如果该结点有子结点, 则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。 三、解题代码 public class Test {
一、题目 请完成一个函数,输入一个二叉树,该函数输出它的镜像。 二、解题思路 先前序遍历这棵树的每个结点,如果遍历到的结点有子结点,就交换它的两个子结点。当交换完所有非叶子结点的左右子结点之后,就得到了树的镜像。 三、解题代码 public class Test { /** * 二叉树的树结点 */ public static class BinaryTreeN
一、题目 输入两棵二叉树A 和B,判断B 是不是A 的子结构。 二、解题思路 要查找树A 中是否存在和树B 结构一样的子树,我们可以分成两步: 第一步在树A 中找到和B 的根结点的值一样的结点R, 第二步再判断树A 中以R 为根结点的子树是不是包含和树B 一样的结构。 三、解题代码 public class Test { /** * 二叉树的树结点 */ pub
一、题目 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如:前序遍历序列{ 1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8,6},重建二叉树并输出它的头结点。 二、解题思路 由前序遍历的第一个节点可知根节点。根据根节点,可以将中序遍历划分成左右子树。在前序遍历中找出对应的左右子
一、概念 Binary Tree(二叉树):二叉树的每个节点最多有两个子节点 Binary Search Tree(二叉搜索树):二叉搜索树每个节点只存储一个键值,并且左子树(如果有)所有节点的值都要小于根节点的值,右子树(如果有)所有节点的值都要大于根节点的值。 B-Tree(Balanced Tree):也就是今天要说的B-树,这里的-不是minus的意思,而是作为连接符的横杠,而我们也经常把
一、AVL树 AVL树是高度平衡的而二叉树。它的特点是:AVL树中任何节点的两个子树的高度最大差别为1。 上面的两张图片,左边的是AVL树,它的任何节点的两个子树的高度差别都<=1;而右边的不是AVL树,因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3,而以8为根节点的树的高度是1)。 二、红黑树 R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查
一、树的介绍 1.树的定义 树是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。 把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点: (01) 每个节点有零个或多个子节点; (02) 没有父节点的节点称为根节点; (03) 每一个非根节点有且只有一个父节点; (04) 除了根节点外,每个子节点可以分为多个不相交的子树。 2.树的基