算法题--二叉树单条相连路径元素的最大和

2020-05-04 本文已影响0人岁月如歌2020

image.png

0. 链接

1. 题目

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

2. 思路1: 递归

基本思路是自底向上, 最底层的情况, 是本节点的值+左子节点的值+右子节点的值, 去试图更新最大值
然后取出左右子节点较大的值, 与本节点一起继续往上追溯
在追溯到每个节点的地方, 又可以计算左右子树最佳路径累计和，去试图更新最大值，这个处理逻辑与第一步的处理逻辑重复, 因此可以使用递归
时间复杂度: ```O(N)``
空间复杂度: O(logN)

3. 代码

# coding:utf8


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def maxPathSum(self, root: TreeNode) -> int:

        max_value = None

        def check(node):
            nonlocal max_value
            if node is None:
                return 0
            left = max(0, check(node.left))
            right = max(0, check(node.right))
            # 子树要试图成为最大值
            if max_value is not None:
                max_value = max(max_value, left + right + node.val)
            else:
                max_value = left + right + node.val
            # 选择较大的一边, 继续往上寻根
            return max(left, right) + node.val

        check(root)
        return max_value


solution = Solution()

root1 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(3)
print(solution.maxPathSum(root1))

root2 = node = TreeNode(-10)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)
print(solution.maxPathSum(root2))

root3 = node = TreeNode(-3)
print(solution.maxPathSum(root3))

root4 = node = TreeNode(-2)
node.left = TreeNode(-1)
print(solution.maxPathSum(root4))


root5 = node = TreeNode(-1)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)
print(solution.maxPathSum(root5))

输出结果

4. 结果