面试刷题：分裂二叉树的最大乘积
By 青衣极客 Blue Geek In 2020-04-02
“递归”是一个会让每个初学计算机编程的人都头晕的概念，但是它简单的形式又让我们在描述和解决问题时有了极大的便利。大家理解“递归”通常就是指“自己调用自己”这种很绕口的逻辑，其实质是子问题与父级问题具有相同的逻辑结构，只是数据内容存在差异，所以在求解子问题上适用父问题的解决方案。在处理树形结构时，“递归”是一种常用的算法。二叉树作为最简单也是最常用的树形结构，在Leetcode中也是频繁出现。这里就以Q1339问题简要讨论一下“递归”。
1. 题目 Q1339 分裂二叉树的最大乘积
给定二叉树的root。通过删除一个边，将二叉树分成两个子树，以使子树之和的乘积最大化。 由于答案可能太大，请以10 ^ 9 + 7为模返回。
约束条件：
(a) 每棵树的节点数量在[2,50000]范围内
(b) 每棵树存储的值在[1,10000]范围内
示例1
Input: root = [1,2,3,4,5,6]
Output: 110
解释： 移除“1”和“2”之间的边，所得的两个子树的和分别为11、10，它们的乘积是110。
示例2
Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
解释： 移除“2”与“4”之间的边，所得两个子树的和分别为6、15，他们的乘积是90.
示例3
Input: root = [2,3,9,10,7,8,6,5,4,11,1]
Output: 1025
示例4
Input: root = [1,1]
Output: 1
2. 求解思路
很快有了一个最直观的思路：在移除一条边时，分别计算新形成的两棵树中元素之和，然后记录乘积；遍历所有的边，尝试移除操作，最后选择出最大的乘积即可。
这个思路是否有可以优化的点呢？至少有一点，可以先将每个节点上所记录的数组修改为其所在子树上所有节点的和，这样一次遍历即可完成，而不需每次都重复计算。这个预处理操作使用“递归”来实现也是非常简单的。每个节点的值应当是其本身存储的值以及其左右子树各自和的叠加，这一描述构成了逻辑上的重复和递推。以下代码可以准确描述这种逻辑：
int _total_sum(TreeNode * root) {
if (!root) {
return 0;
}
root->val += _total_sum(root->left);
root->val += _total_sum(root->right);
return root->val;
}
接着需要进行操作就是尝试移除每一个边，然后保存乘积最大的值即可，这一步也可以使用递归完成。
3. 解决方案
这里提供一种使用递归求解的C++解决方案。
class Solution {
private:
int _total_sum(TreeNode * root) {
if (!root) {
return 0;
}
root->val += _total_sum(root->left);
root->val += _total_sum(root->right);
return root->val;
}
long _find_max_prod(TreeNode * root, const int & total) {
if ((!root->left) && (!root->right)) {
return 0;
}
long left = 0, right = 0;
if (root->left) {
left = (long)(root->left->val) * (total - root->left->val);
left = max(left, _find_max_prod(root->left, total));
}
if (root->right) {
right = (long)(root->right->val) * (total - root->right->val);
right = max(right, _find_max_prod(root->right, total));
}
return max(left, right);
}
public:
// Runtime: 160 ms, faster than 76.35%
// Memory Usage: 68.8 MB, less than 100.00%
int maxProduct(TreeNode* root) {
int total = _total_sum(root);
long ret = _find_max_prod(root, total);
return ret % (1000000000 + 7);
}
};
从这个解决方案来看，两个子函数分别完成“子树求和”与“枚举所有边”这两个功能。从代码中可以看出，虽然这两个子函数完成的功能不同，但是其逻辑结构是非常相似的。都是先确定“递归”结束条件，然后分别对左子树和右子树进行同样的逻辑操作。这也说明了“递归”的两大重点：(1)设置结束条件，(2)针对子结构重复调用。如果没有正确设置重点(1)，可能会出现无穷递归，从而导致堆栈溢出的错误；如果没有正确编写重点(2)，则会造成最终结果可能不正确。
当提到“重复调用”时，我们很容易联想到“循环”，事实上“循环”的作用就是为了简化重复逻辑的，那么“循环”与“递归”有什么区别呢？简单来说，“循环”是指时间上的重复，“递归”是指结构上的重复。事实上，所有的“递归逻辑”都可以使用“循环”来实现。而且由于避免了频繁的压入和弹出堆栈，还能有不少执行效率上的提升。但其缺点也很明显，即逻辑的实现形式非常复杂，有时还具有很强的技巧，不是那么容易实现的。通常只有在资源极其紧缺的情况下才考虑使用“循环”来实现“递归逻辑”。在Leetcode中，我们还是最好直接使用“递归”形式的实现，毕竟刷题追求的是训练解决问题的算法设计思路。
COMMENT
博客评论区功能由Github Issue提供，提交Issue时请以本文标题为话题。
"BG79-面试刷题：分裂二叉树的最大乘积 Q1339"