LeetCode 5330. Maximum-Product-of-Splitted-Binary-Tree

题目链接

题意

给你二叉树,让你切断一条边将其分为两部分使得这两部分和的乘积最大

思路:

这就是一道很水的递归题啊,显然当两部分的和尽可能相等的时候(也就是各位总和二分之一)最大。
递归就行复杂度$O(n)$,空间复杂度$O(height)$
主要是记录下python的recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def maxProduct(self, root):
self.max_pro = sum = 0
def dfs(root):
if not root: return 0
lsum, rsum = dfs(root.left), dfs(root.right)
self.max_pro = max(self.max_pro, lsum * (sum - lsum), rsum * (sum - rsum))
return root.val + lsum + rsum
sum = dfs(root)
dfs(root)
return self.max_pro % (10**9 + 7)


-------------本文结束感谢您的阅读-------------


本文标题:LeetCode 5330. Maximum-Product-of-Splitted-Binary-Tree

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2020年02月02日 - 13:02

最后更新:2020年02月02日 - 13:02

原始链接:https://statusrank.xyz/articles/220c2a9e.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: