5.6日华为笔试第三题解法
程序员文章站
2024-03-15 16:23:42
...
点赞再看,养成习惯!
题目描述
输入一个字符串,代表一颗二叉树,如"2(1,2(0,1)",树结构如下:
规则就是:1.某结点的子结点就用括号括起来并用逗号隔开;2.只有一个子结点,另一个为空,那就用0表示;3.一个子结点都没有,也就没有括号。
然后,在树中找出最大的路段和,路段指的是从根结点到叶子结点的路径中的一段(可以包含根节点)权值和。
解题方案
解题思路
1.根据输入的字符串构造出二叉树;
给定的字符串其实是用广义表表示的二叉树,第一步要解决的问题就是如何转换广义表为对应的二叉树
2.递归+动态规划来求出最大路段和。
这个很类似力扣上求二叉树的最大路径和,有所区别的是路段不会是两个叶子结点之间的路径,所以稍微修改最大路径和的解决方法即可解决这个问题。
py代码
def buildTreeFromGenList(arr):
'''
转化广义表为对应的二叉树
:param arr: 广义表对应有效字符组成的数组
:return: 二叉树的根结点
'''
stack = []
k = -1
for i in range(len(arr)):
if arr[i] == '(':
k = 0
stack.append(arr[i])
elif arr[i] == ',':
k = 1
elif arr[i] == ')':
stack.pop()
else:
if arr[i] == '0':
node = None
else:
node = TreeNode(int(arr[i]))
if k == -1:
stack.append(node)
elif k == 0:
stack.pop()
stack[-1].left = node
stack.append(node)
elif k == 1:
stack.pop()
stack[-1].right = node
stack.append(node)
return stack[-1]
def max_gain(node):
'''
求取最大路段和
:param node: 二叉树的根结点
:return: 包含node的最大路段和
'''
global max_sum
if not node:
return 0
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
price_newpath = max(left_gain, right_gain) + node.val
max_sum = max(max_sum, price_newpath)
return node.val + max(left_gain, right_gain)
if __name__ == '__main__':
'''
测试用例:
2
2(0,1)
2(1,2(0,1))
1(-2(3,-4),5(-6,7))
对应输出:
2
3
5
13
'''
line = input()
if not line:
print(0)
# 1.转化字符串为有效字符的组合
arr = [] # 存储字符串转化来的有效字符组合的数组
i, j = 0, 1
while i < len(line):
while j < len(line) and line[j].isdigit():
j += 1
arr.append(line[i:j])
if j<len(line):
arr.append(line[j])
if j + 1 < len(line) and (line[j + 1] == ',' or line[j + 1] == ')'):
arr.append(line[j + 1])
i = j + 2
else:
i = j + 1
j = i + 1
# 2.根据广义表构造二叉树
root = buildTreeFromGenList(arr)
max_sum = float('-inf')
# 3.求取最大路段和
max_gain(root)
print(max_sum)
时间复杂度为O(N),N为字符串的长度。
参考文献
1.https://blog.csdn.net/alex1997222/article/details/82944763(广义表转化为二叉树的博客)
2.https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/(二叉树的最大路径和)
觉得不错,就点个赞吧!
上一篇: HUAWEI(22)——ISIS
下一篇: PAT 108