Kotlin程序员面试算法宝典【1.7】

3.3 如何从顶部开始逐层打印二叉树结点数据

【出自 WR 面试题】

给定一棵二叉树，要求逐层打印二叉树结点的数据，例如有如下二叉树：

对这棵二叉树层序遍历的结果为 1， 2， 3， 4， 5， 6， 7。

分析与解答：

为了实现对二叉树的层序遍历，就要求在遍历一个结点的同时记录下它的孩子结点的信息，然后按照这个记录的顺序来访问结点的数据，在实现的时候可以采用队列来存储当前遍历到的结点的孩子结点，从而实现二叉树的层序遍历，遍历过程如下图所示：

在上图中，图（ 1）首先把根结点 1 放到队列里面，然后开始遍历。图（ 2）队列首元素（结点 1）出队列，同时它的孩子结点 2 和结点 3 进队列。图（ 3）接着出队列的结点为 2，同时把它的孩子结点 4 和结点 5 放到队列里，依此类推就可以实现对二叉树的层序遍历。

实现代码如下：

import java.util.LinkedList /** * 用层序遍历的方式打印出二叉树结点的内容 * @param root 二叉树根结点 */ fun printTreeLayer（root： BiTNode？） { if （root == null） return var p： BiTNode val queue = LinkedList<BiTNode>（） //树根结点进队列 queue.offer（root） while （queue.size >0） { p = queue.poll（） //访问当前结点 print（"${p.data} "） //如果这个结点的左孩子不为空则入队列 if （p.lChild ！= null） queue.offer（p.lChild） //如果这个结点的右孩子不为空则入队列 if （p.rChild ！= null） queue.offer（p.rChild） } } fun main（args： Array<String>） { val arr = intArrayOf（1， 2， 3， 4， 5， 6， 7， 8， 9， 10） val root = arrayToTree（arr， 0， arr.size - 1） //3.2 节 print（"树的层序遍历结果为："） printTreeLayer（root） }

测试数据采用了 3.2 节所构造的数，程序的运行结果如下：

树的层序遍历结果为：6 3 9 2 5 8 10 1 4 7

算法性能分析：

在二叉树的层序遍历过程中，对树中的各个结点只进行了一次访问，因此，时间复杂度为 O（N），此外，这种方法还使用了队列来保存遍历的中间结点，所使用队列的大小取决于二叉树中每一层中结点个数的最大值。具有 N 个结点的完全二叉树的深度为 h=log2N+1。而深

度为 h 的这一层最多的结点个数为 2h-1=n/2。也就是说队列中可能的最多的结点个数为 N/2。因此，这种算法的空间复杂度为 O（N）。

引申：用空间复杂度为 O（1）的算法来实现层序遍历

上面介绍的算法的空间复杂度为 O（N），显然不满足要求。通常情况下，提高空间复杂度都是要以牺牲时间复杂度作为代价的。对于本题而言，主要的算法思路是：不使用队列来存储每一层遍历到的结点，而是每次都会从根结点开始遍历。把遍历二叉树的第 k 层的结点，转换为遍历二叉树根结点的左右子树的第 k-1 层结点。算法如下：

fun printAtLevel（root： BiTNode？， level： Int）： Int { return when { root == null || level <0 -> 0 level == 0 -> { println（root.data） 1 } else -> { /* 把打印根结点 level 层的结点转换为求解根结点的孩子结点的 level-1 层的结点。 */ printAtLevel（root.lChild， level - 1） + printAtLevel（root.rChild， level - 1） } } }

通过上述算法，可以首先求解出二叉树的高度 h，然后调用上面的函数 h 次就可以打印出每一层的结点。

3.4 如何求一棵二叉树的最大子树和

【出自 WR 面试题】

给定一棵二叉树，它的每个结点都是正整数或负整数，如何找到一棵子树，使得它所有结点的和最大？

分析与解答：

要求一棵二叉树的最大子树和，最容易想到的办法就是针对每棵子树，求出这棵子树中所有结点的和，然后从中找出最大值。恰好二叉树的后序遍历就能做到这一点。在对二叉树进行后序遍历的过程中，如果当前遍历的结点的值与其左右子树和的值相加的结果大于最大值，则更新最大值。如下图所示：

在上面这个图中，首先遍历结点-1，这个子树的最大值为-1，同理，当遍历到结点 9 时，子树的最大值为 9，当遍历到结点 3 的时候，这个结点与其左右孩子结点值的和（ 3-1+9=11）大于最大值（ 9）。因此，此时最大的子树为以 3 为根结点的子树，依此类推直到遍历完整棵树为止。实现代码如下：
 

private var maxSum = Integer.MIN_VALUE /** * 方法功能：求最大子树 * @param root 根结点 * @param maxRoot 最大子树的根结点 * @return 以 root 为根结点子树所有结点的和 */ fun findMaxSubTree（root： BiTNode？， maxRoot： BiTNode）： Int { if （root == null） { return 0 } //求 root 左子树所有结点的和 val lMax = findMaxSubTree（root.lChild， maxRoot） //求 root 右子树所有结点的和 val rMax = findMaxSubTree（root.rChild， maxRoot） val sum = lMax + rMax + root.data //以 root 为根的子树的和大于前面求出的最大值 if （sum >maxSum） { maxSum = sum maxRoot.data = root.data } //返回以 root 为根结点的子树的所有结点的和 return sum } /** * 构造二叉树 * @return 返回新构造的二叉树的根结点 */ 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 main（args： Array<String>） { //构造二叉树 val root = constructTree（） val maxRoot = BiTNode（） //最大子树的根结点 findMaxSubTree（root， maxRoot） println（"最大子树和为： $maxSum"） println（"对应子树的根结点为： ${maxRoot.data}"） }

程序的运行结果如下：

最大子树和为： 11

对应子树的根结点为： 3

算法性能分析：

这种方法与二叉树的后序遍历有相同的时间复杂度，即为 O（N），其中， N 为二叉树的结点个数。

3.5 如何判断两棵二叉树是否相等

【出自 BD 面试题】

难度系数： ★★★☆☆ 被考察系数：★★★★☆

题目描述：

两棵二叉树相等是指这两棵二叉树有着相同的结构，并且在相同位置上的结点有相同的值。如何判断两棵二叉树是否相等？

分析与解答：

如果两棵二叉树 root1、 root2 相等，那么 root1 与 root2 结点的值相同，同时它们的 左 右 孩 子 也 有 着 相 同 的 结 构 ， 并 且 对 应 位 置 上 结 点 的 值 相 等 ， 即 root1.data== root2.data，并且 root1 的左子树与 root2 的左子树相等， root1 的右子树与 root2 的右子树相等。根据这个条件，可以非常容易地写出判断两棵二叉树是否相等的递归算法。实现代码如下：

/** * 判断两棵二叉树是否相等 * @param root1 两棵二叉树的根结点 * @param root2 两棵二叉树的根结点 * @return 如果两棵树相等则返回 true，否则返回 false */ fun isEqual（root1： BiTNode？， root2： BiTNode？）： Boolean { if （root1 == null && root2 == null） return true if （root1 == null && root2 ！= null） return false if （root1 ！= null && root2 == null） return false return if （root1？.data == root2？.data） isEqual（root1？.lChild， root2？.lChild） &&isEqual（root1？.rChild， root2？.rChild） else false } fun main（args： Array<String>） { val root1 = constructTree（） //3.4 节 val root2 = constructTree（） val equal = isEqual（root1， root2） if （equal） println（"这两棵树相等"） else println（"这两棵树不相等"） }

程序的运行结果如下：

这两棵树相等

算法性能分析：

这种方法对两棵树只进行了一次遍历，因此，时间复杂度为 O（N）。此外，这种方法没有申请额外的存储空间。

3.6 如何把二叉树转换为双向链表

【出自 XL 笔试题】

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整结点的指向。例如：

分析与解答：

由于转换后的双向链表中结点的顺序与二叉树的中序遍历的顺序相同，因此，可以对二叉树的中序遍历算法进行修改，通过在中序遍历的过程中修改结点的指向来转换成一个排序的双向链表。实现思路如下图所示：假设当前遍历的结点为 root， root 的左子树已经被转换为双向链表（如下图（ 1）所示），使用两个变量 pHead 与 pEnd 分别指向链表的头结点与尾结点。那么在遍历 root 结点的时候，只需要将 root 结点的 lchild（左）指向 pEnd，把pEnd 的 rchild（右）指向 root；此时 root 结点就被加入到双向链表里了，因此， root 变成了双向链表的尾结点。对于所有的结点都可以通过同样的方法来修改结点的指向。因此，可以采用递归的方法来求解，在求解的时候需要特别注意递归的结束条件以及边界情况（例如双向链表为空的时候）。

实现代码如下： private var pHead： BiTNode？ = null//双向链表头结点 private var pEnd： BiTNode？ = null //双向链表尾结点 /** * 把二叉树转换为双向列表 * @param root 二叉树根结点 */ fun inOrderBSTree（root： BiTNode？） { if （null == root） { return } //转换 root 的左子树 inOrderBSTree（root.lChild） root.lChild = pEnd //使当前结点的左孩子指向双向链表中最后一个结点 if （null == pEnd） { //双向列表为空，当前遍历的结点为双向链表的头结点 pHead = root } else { //使双向链表中最后一个结点的右孩子指向当前结点 pEnd？.rChild = root } pEnd = root //将当前结点设为双向链表中最后一个结点 //转换 root 的右子树 inOrderBSTree（root.rChild） } fun main（args： Array<String>） { val arr = intArrayOf（1， 2， 3， 4， 5， 6， 7） val root = arrayToTree（arr， 0， arr.size - 1） //3.2 节 inOrderBSTree（root） var cur： BiTNode？ print（"转换后双向链表正向遍历： "） cur = pHead while （cur ！= null） { print（"${cur.data} "） cur = cur.rChild } println（） print（"转换后双向链表逆向遍历： "） cur = pEnd while （cur ！= null） { print（"${cur.data} "） cur = cur.lChild } }

程序的运行结果如下： 转换后双向链表正向遍历： 1 2 3 4 5 6 7 转换后双向链表逆向遍历： 7 6 5 4 3 2 1

算法性能分析：

这种方法与二叉树的中序遍历有着相同的时间复杂度 O（N）。此外，这种方法只用了两个额外的变量 pHead 与 pEnd 来记录双向链表的首尾结点，因此，空间复杂度为 O（1）。