欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

5.6日华为笔试第三题解法

程序员文章站 2024-03-15 16:23:42
...

点赞再看,养成习惯!

题目描述

输入一个字符串,代表一颗二叉树,如"2(1,2(0,1)",树结构如下:
5.6日华为笔试第三题解法
规则就是: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