BG79 面试刷题：分裂二叉树的最大乘积

【原创】From 青衣极客 Blue Geek In 2020-04-03

“递归”是一个会让每个初学计算机编程的人都头晕的概念，但是它简单的形式又让我们在描述和解决问题时有了极大的便利。

1. 题目 Q1339 分裂二叉树的最大乘积

给定二叉树的 root。通过删除一个边，将二叉树分成两个子树，以使子树之和的乘积最大化。由于答案可能太大，请以10 ^ 9 + 7为模返回。

约束条件：

<code>(a) 每棵树的节点数量在[2,50000]范围内
(b) 每棵树存储的值在[1,10000]范围内/<code>

示例1

<code>Input: root = [1,2,3,4,5,6]
Output: 110/<code>

解释： 移除“1”和“2”之间的边，所得的两个子树的和分别为11、10，它们的乘积是110。

示例2

<code>Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90/<code>

解释： 移除“2”与“4”之间的边，所得两个子树的和分别为6、15，他们的乘积是90.

示例3

<code>Input: root = [2,3,9,10,7,8,6,5,4,11,1]
Output: 1025/<code>

示例4

<code>Input: root = [1,1]
Output: 1/<code>

2. 求解思路

很快有了一个最直观的思路：在移除一条边时，分别计算新形成的两棵树中元素之和，然后记录乘积；遍历所有的边，尝试移除操作，最后选择出最大的乘积即可。

这个思路是否有可以优化的点呢？至少有一点，可以先将每个节点上所记录的数组修改为其所在子树上所有节点的和，这样一次遍历即可完成，而不需每次都重复计算。这个预处理操作使用“递归”来实现也是非常简单的。每个节点的值应当是其本身存储的值以及其左右子树各自和的叠加，这一描述构成了逻辑上的重复和递推。以下代码可以准确描述这种逻辑：

接着需要进行操作就是尝试移除每一个边，然后保存乘积最大的值即可，这一步也可以使用递归完成。

3. 解决方案

这里提供一种使用递归求解的C++解决方案。

从这个解决方案来看，两个子函数分别完成“子树求和”与“枚举所有边”这两个功能。从代码中可以看出，虽然这两个子函数完成的功能不同，但是其逻辑结构是非常相似的。都是先确定“递归”结束条件，然后分别对左子树和右子树进行同样的逻辑操作。这也说明了“递归”的两大重点：(1)设置结束条件，(2)针对子结构重复调用。如果没有正确设置重点(1)，可能会出现无穷递归，从而导致堆栈溢出的错误；如果没有正确编写重点(2)，则会造成最终结果可能不正确。

当提到“重复调用”时，我们很容易联想到“循环”，事实上“循环”的作用就是为了简化重复逻辑的，那么“循环”与“递归”有什么区别呢？简单来说，“循环”是指时间上的重复，“递归”是指结构上的重复。事实上，所有的“递归逻辑”都可以使用“循环”来实现。而且由于避免了频繁的压入和弹出堆栈，还能有不少执行效率上的提升。但其缺点也很明显，即逻辑的实现形式非常复杂，有时还具有很强的技巧，不是那么容易实现的。

閱讀更多 青衣極客 的文章

關鍵字: 刷题 示例 二叉树