网站源码超市永兴网站开发

张

张建站

2026/4/7 7:36:58

10分钟阅读

网站源码超市,永兴网站开发,公司企业网站建设步骤,discuz做服务网站3.7 如何判断一个数组是否是二元查找树后序遍历的序列【出自 ALBB 面试题】难度系数#xff1a; ★★★★☆ 题目描述#xff1a;被考察系数#xff1a;★★★★☆输入一个整数数组#xff0c;判断该数组是否是某二元查找树的后序遍历的结果。如果是#xff0c;那么返回 t…3.7 如何判断一个数组是否是二元查找树后序遍历的序列【出自 ALBB 面试题】难度系数 ★★★★☆ 题目描述被考察系数★★★★☆输入一个整数数组判断该数组是否是某二元查找树的后序遍历的结果。如果是那么返回 true否则返回 false。例如数组{1325764}就是下图中二叉树的后序遍历序列。分析与解答二元查找树的特点是对于任意一个结点它的左子树上所有结点的值都小于这个结点的值它的右子树上所有结点的值都大于这个结点的值。根据它的这个特点以及二元查找树后序遍历的特点可以看出这个序列的最后一个元素一定是树的根结点上图中的结点 4然后在数组中找到第一个大于根结点 4 的值 5那么结点 5 之前的序列 132对应的结点一定位于结点 4 的左子树上结点 5包含这个结点后面的序列一定位于结点 4 的右子树上也就是说结点 5 后面的所有值都应该大于或等于 4。对于结点 4 的左子树遍历的序列{132}以及右子树的遍历序列{576}可以采用同样的方法来分析因此可以通过递归方法来实现实现代码如下/** * 判断一个数组是否是二元查找树的后续遍历序列 * param arr 数组 * return true是否则返回 false */ fun isAfterOrderarr IntArray start Int end Int Boolean { if arr null { return false } //数组的最后一个结点必定是根结点 val root arr[end] var i Int start var j Int //找到第一个大于 root 的值那么前面所有的结点都位于 root 的左子树上 while i end { if arr[i] root break i } //如果序列是后续遍历的序列那么从 i 开始的所有值都应该大于根结点 root 的值 j i while j end { if arr[j] root return false j } var leftIsAfterOrder true var rightIsAfterOrder true //判断小于 root 值的序列是否是某一二元查找树的后续遍历 if i start leftIsAfterOrder isAfterOrderarr start i - 1 //判断大于 root 值的序列是否是某一二元查找树的后续遍历 if j end rightIsAfterOrder isAfterOrderarr i end return leftIsAfterOrder rightIsAfterOrder } fun mainargs ArrayString { val arr intArrayOf1 3 2 5 7 6 4 val result isAfterOrderarr 0 arr.size - 1 for i in arr.indices print${arr[i]} if result println是某一二元查找树的后续遍历序列 else println不是某一二元查找树的后续遍历序列 }程序的运行结果如下1 3 2 5 7 6 4 是某一二元查找树的后序遍历序列算法性能分析这种方法对数组只进行了一次遍历因此时间复杂度为 ON。3.8 如何找出排序二叉树上任意两个结点的最近共同父结点【出自 WR 面试题】难度系数 ★★★☆☆ 题目描述被考察系数★★★★☆对于一棵给定的排序二叉树求两个结点的共同父结点例如在下图中结点 1 和结点5 的共同父结点为 3。分析与解答方法一路径对比法对于一棵二叉树的两个结点如果知道了从根结点到这两个结点的路径就可以很容易地找出它们最近的公共父结点。因此可以首先分别找出从根结点到这两个结点的路径例如上图中从根结点到结点 1 的路径为 6-3-2-1从根结点到结点 5 的路径为 6-3-5然后遍历这两条路径只要是相等的结点都是它们的父结点找到最后一个相等的结点即为离它们最近的共同父结点在这个例子中结点 3 就是它们共同的父结点。为了便于理解这里仍然使用 3.2 节中构造的二叉树的方法。示例代码如下import java.util.Stack /** * 获取二叉树从根结点 root 到 node 结点的路径 * param root 根结点 * param node 二叉树中的某个结点 * param s 用来存储路径的栈 * return node 在 root 的子树上或 noderoot 时返回 true否则返回 false */ private fun getPathFromRootroot BiTNode node BiTNode s StackBiTNode Boolean { if root null return false if root node { s.pushroot return true } /* * 如果 node 结点在 root 结点的左子树或右子树上 * 那么 root 就是 node 的祖先结点把它加到栈里 */ if getPathFromRootroot.lChild node s || getPathFromRootroot.rChild node s { s.pushroot return true } return false } /** * 查找二叉树中两个结点最近的共同父结点 * param root 根结点 * param node1 二叉树中的结点 * param node2 二叉树中的结点 * return node1 与 node2 最近的共同父结点 */ fun findParentNoderoot BiTNode node1 BiTNode node2 BiTNode BiTNode { val stack1 StackBiTNode //保存从 root 到 node1 的路径 val stack2 StackBiTNode //保存从 root 到 node2 的路径 //获取从 root 到 node1 的路径 getPathFromRootroot node1 stack1 //获取从 root 到 node2 的路径 getPathFromRootroot node2 stack2 var commonParent BiTNode null //获取最靠近 node1 和 node2 的父结点 while stack1.peek stack2.peek { commonParent stack1.peek stack1.pop stack2.pop } return commonParent } fun mainargs ArrayString { val arr intArrayOf1 2 3 4 5 6 7 8 9 10 val root arrayToTreearr 0 arr.size - 1 //3.2 节 nval node1 root.lChild.lChild.lChild val node2 root.lChild.rChild val res root.let { findParentNodeit node1 node2 } if res null print${node1.data.toString}与${node2.data}的最近公共父结点为 ${res.data} else println没有公共父结点 }程序的运行结果如下1 与 5 的最近公共父结点为 3算法性能分析当获取二叉树从根结点 root 到 node 结点的路径时最坏的情况就是把树中所有结点都遍历了一遍这个操作的时间复杂度为 ON再分别找出从根结点到两个结点的路径找它们最近的公共父结点的时间复杂度也为 ON因此这种方法的时间复杂度为 ON。此外这种方法用栈保存了从根结点到特定结点的路径在最坏的情况下这个路径包含了树中所有的结点因此空间复杂度也为 ON。很显然这种方法还不够理想。下面介绍另外一种能降低空间复杂度的方法。方法二结点编号法根据 3.1 节中介绍的性质 5可以把二叉树看成是一棵完全二叉树不管实际的二叉树是否为完全二叉树二叉树中的结点都可以按照完全二叉树中对结点编号的方式进行编号下图为对二叉树中的结点按照完全二叉树中结点的编号方式进行编号后的结果结点右边的数字为其对应的编号。根据 3.1 节性质 5 可以知道一个编号为 n 的结点它的父亲结点的编号为 n/2。假如要求 node1 与 node2 的最近的共同父结点首先把这棵树看成是一棵完全二叉树不管结点是否存在分别求得这两个结点的编号 n1 n2。然后每次找出 n1 与 n2 中较大的值除以 2直到 n1n2 为止此时 n1 或 n2 的值对应结点的编号就是它们最近的共同父结点的编号接着可以根据这个编号信息找到对应的结点具体方法是通过观察二叉树中结点的编号可以发现首先把根结点 root 看成 1求 root 的左孩子编号的方法为把 root 对应的编号看成二进制然后向左移一位末尾补 0如果是 root 的右孩子则末尾补 1因此通过结点位置的二进制码就可以确定这个结点。例如结点 3 的编号为 2二进制 10它的左孩子的求解方法为 10向左移一位末尾补 0可以得到二进制 100十进制 4位置为 4 的结点的值为 2。从这个特性可以得出通过结点位置信息获取结点的方法例如要求位置 4 的结点 4 的二进制码为 100由于 1 代表根结点接下来的一个 0 代表是左子树 root.lchild最后一个 0 也表示左子树root.lchild.lchild通过这种方法非常容易根据结点的编号找到对应的结点。实现代码如下class IntRef { var num Int 0 } /** * 找出结点在二叉树中的编号 * param root 根结点 * param node 待查找结点 * param number node 结点在二叉树中的编号 * return true找到该结点的位置否则返回 false */ private fun getNoroot BiTNode node BiTNode number IntRef Boolean { if root null return false if root node return true val tmp number.num number.num 2 * tmp // node 结点在 root 的左子树中左子树编号为当前结点编号的 2 倍 return if getNoroot.lChild node number { true // node 结点在 root 的右子树中右子树编号为当前结点编号的 2 倍加 1 } else { number.num tmp * 2 1 getNoroot.rChild node number } } /** * 根据结点的编号找出对应的结点 * param root 根结点 * param number 为结点的编号 * return 编号为 number 对应的结点 **/ private fun getNodeFromNumroot BiTNode number Int BiTNode { var rootNode root var num number if rootNode null || num 0 return null if num 1 return rootNode // 结点编号对应二进制的位数最高位一定为 1因为根结点代表 1 var len Math.lognum.toDouble / Math.log2.0.toInt // 去掉根结点表示的 1 num - 1 shl len while len 0 { /* * 如果这一位二进制的值为 1 * 那么编号为 number 的结点必定在当前结点的右子树上 */ rootNode if 1 shl len - 1 and num 1 rootNode.rChild else rootNode.lChild len-- } return rootNode } /** * 查找二叉树中两个结点最近的共同父结点 * param root 根结点 * param node1 二叉树中的结点 * param node2 二叉树中的结点 * return node1 与 node2 最近的共同父结点 */ fun findParentNoderoot BiTNode node1 BiTNode node2 BiTNode BiTNode { val ref1 IntRef ref1.num 1 val ref2 IntRef ref2.num 1 getNoroot node1 ref1 getNoroot node2 ref2 var num1 ref1.num var num2 ref2.num // 找出编号为 num1 和 num2 的共同父结点 while num1 num2 { if num1 num2 num1 / 2 else num2 / 2 } // num1 就是它们最近的公共父结点的编号通过结点编号找到对应的结点 return getNodeFromNumroot num1 } fun mainargs ArrayString { val arr intArrayOf1 2 3 4 5 6 7 8 9 10 val root arrayToTreearr 0 arr.size - 1 //3.2 节 val node1 root.lChild.lChild.lChild val node2 root.lChild.rChild val res root.let { findParentNodeit node1 node2 } if res null print${node1.data.toString}与${node2.data}的最近公共父结点为 ${res.data} else println没有公共父结点 }算法性能分析这种方法的时间复杂度也为 ON与方法一相比在求解的过程中只用了个别的几个变量因此空间复杂度为 O1。方法三后序遍历法很多与二叉树相关的问题都可以通过对二叉树的遍历方法进行改装而求解。对于本题而言可以通过对二叉树的后序遍历进行改编而得到。具体思路是查找结点 node1 与结点node2 的最近共同父结点可以转换为找到一个结点 node使得 node1 与 node2 分别位于结点node 的左子树或右子树中。例如题目中的图结点 1 与结点 5 的最近共同父结点为结点 3因为结点 1 位于结点 3 的左子树上而结点 5 位于结点 3 的右子树上。实现代码如下fun findParentNoderoot BiTNode node1 BiTNode node2 BiTNode BiTNode { if null root || root node1 || root node2 { return root } val lChild findParentNoderoot.lChild node1 node2 val rChild findParentNoderoot.rChild node1 node2 return when { // root 的左子树中没有结点 node1 和 node2那么一定在 root 的右子树上 null lChild - rChild // node1 与 node2 分别位于 root 的左子树与右子树上 root 就是它们最近的共同父结点 null rChild - lChild // root 的右子树中没有结点 node1 和 node2那么一定在 root 的左子树上 else - root } } fun mainargs ArrayString { val arr intArrayOf1 2 3 4 5 6 7 8 9 10 val root arrayToTreearr 0 arr.size - 1 //3.2 节 val node1 root.lChild.lChild.lChild val node2 root.lChild.rChild val res root.let { findParentNodeit node1 node2 } if res null print${node1.data.toString}与${node2.data}的最近公共父结点为 ${res.data} else println没有公共父结点 }把方法一中的 FindParentNode 替换为本方法的 FindParentNode可以得到同样的输出结果。算法性能分析这种方法与二叉树的后序遍历方法有着相同的时间复杂度 ON。引申如何计算二叉树中两个结点的距离【出自 TX 面试题】题目描述在没有给出父结点的条件下计算二叉树中两个结点的距离。两个结点之间的距离是从一个结点到达另一个结点所需的最小的边数。例如给出下面的二叉树Dist452 Dist464。分析与解答对于给定的二叉树 root只要能找到两个结点 n1 与 n2 最低的公共父结点 parent那么就可以通过下面的公式计算出这两个结点的距离Distn1 n2 Distroot n1 Distroot n2 - 2*Distroot parent3.9 如何复制二叉树【出自 GG 面试题】难度系数 ★★★☆☆ 题目描述被考察系数★★★★☆给定一个二叉树根结点复制该树返回新建树的根结点。分析与解答用给定的二叉树的根结点 root 来构造新的二叉树的方法首先创建新的结点 dupTree然后根据 root 结点来构造 dupTree 结点 dupTree.dataroot.data最后分别用 root 的左右子树来构造 dupTree 的左右子树。根据这个思路可以实现二叉树的复制使用递归方式实现的代码如下fun createDupTreeroot BiTNode BiTNode { if root null return null //二叉树根结点 val dupTree BiTNode dupTree.data root.data //复制左子树 dupTree.lChild createDupTreeroot.lChild //复制右子树 dupTree.rChild createDupTreeroot.rChild return dupTree } fun constructTree BiTNode { val root BiTNode val node1 BiTNode val node2 BiTNode val node3 BiTNode val node4 BiTNode root.data 6 node1.data 3 node2.data -7 node3.data -1 node4.data 9 root.lChild node1 root.rChild node2 node1.lChild node3 node1.rChild node4 node4.rChild null node4.lChild node4.rChild node3.rChild node4.lChild node3.lChild node3.rChild node2.rChild node3.lChild node2.lChild node2.rChild return root } fun printTreeMidOrderroot BiTNode { if root null return //遍历 root 结点的左子树 if root.lChild null printTreeMidOrderroot.lChild //遍历 root 结点 print${root.data} //遍历 root 结点的右子树 if root.rChild null printTreeMidOrderroot.rChild } fun mainargs ArrayString { val root1 constructTree val root2 createDupTreeroot1 print原始二叉树中序遍历 printTreeMidOrderroot1 println print新的二叉树中序遍历 printTreeMidOrderroot2 }程序的运行结果如下原始二叉树中序遍历-1 3 9 6 -7新的二叉树中序遍历-1 3 9 6 -7算法性能分析这种方法对给定的二叉树进行了一次遍历因此时间复杂度为 ON此外这种方法需要申请 N 个额外的存储空间来存储新的二叉树。3.10 如何在二叉树中找出与输入整数相等的所有路径【出自 BD 面试题】难度系数 ★★★★☆ 题目描述被考察系数★★★★☆从树的根结点开始往下访问一直到叶子结点经过的所有结点形成一条路径。找出所有的这些路径使其满足这条路径上所有结点数据的和等于给定的整数。例如给定如下二叉树与整数 8满足条件的路径为 6-3--1 63-18。分析与解答可以通过对二叉树的遍历找出所有的路径然后判断各条路径上所有结点的值的和是否与给定的整数相等如果相等则打印出这条路径。具体实现方法可以通过对二叉树进行先序遍历来实现实现思路为对二叉树进行先序遍历把遍历的路径记录下来当遍历到叶子结点时判断当前的路径上所有结点数据的和是否等于给定的整数如果相等则输出路径信息示例代码如下import java.util.Vector /** * 打印出满足所有结点数据的和等于 num 的所有路径 * param root 二叉树根结点 * param num 给定的整数 * param s 当前路径上所有结点的和 * param v 用来存储从根结点到当前遍历到结点的路径 */ fun FindRoadroot BiTNode num Int s Int v VectorInt { var sum s //记录当前遍历的 root 结点 sum root.data v.addroot.data //当前结点是叶子结点且遍历的路径上所有结点的和等于 num if root.lChild null root.rChild null sum num { for i in v.indices print${v[i]} println } //遍历 root 的左子树 root.lChild.apply { FindRoadthis num sum v } //遍历 root 的右子树 root.rChild.apply { FindRoadthis num sum v } //清除遍历的路径 sum - v[v.size - 1] v.removeAtv.size - 1 } fun constructTree BiTNode { val root BiTNode val node1 BiTNode val node2 BiTNode val node3 BiTNode val node4 BiTNode root.data 6 node1.data 3 node2.data -7 node3.data -1 node4.data 9 root.lChild node1 root.rChild node2 node1.lChild node3 node1.rChild node4 node4.rChild null node4.lChild node4.rChild node3.rChild node4.lChild node3.lChild node3.rChild node2.rChild node3.lChild node2.lChild node2.rChild return root } fun mainargs ArrayString { val root constructTree //3.5 节 val s VectorInt print满足路径结点和等于 8 的路径为 FindRoadroot 8 0 s }程序的运行结果如下满足路径结点和等于 8 的路径为 6 3 -1算法性能分析这种方法与二叉树的先序遍历有着相同的时间复杂度 ON此外这种方法用一个数组存放遍历路径上结点的值在最坏的情况下时间复杂度为 ON所有结点只有左子树或所有结点只有右子树因此空间复杂度为 ON。