python7.4.2二叉树路径问题及LeetCode题目解析

  下面题目中的路径,定义有所延伸,在解法思路及时间空间复杂度上有所挑战。

  437. Path Sum III

  You are given a binary tree in which each node contains an integer value.

  Find the number of paths that sum to a given value.

  The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

  The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

  Example:

  root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

  10

  / \

  5 -3

  / \ \

  3 2 11

  / \ \

  3 -2 1

  Return 3. The paths that sum to 8 are:

  1. 5 -> 3

  2. 5 -> 2 -> 1

  3. -3 -> 11

  题目解析:

  此题的路径延伸至任一结点至其子孙结点的路径,解法一,速度将近1s,非常慢,但是写法简洁,思路也是最为直接的一种,对这棵树前序遍历,调用dfs函数,求从该结点起至任一子结点的路径和是否为sum。该方法效果低的原因就是大量重复遍历。

  class Solution:

  def pathSum(self, root: TreeNode, sum: int) -> int:

  """

  :type root: TreeNode

  :type sum: int

  :rtype: int

  """

  def dfs(node, sum):

  return dfs(node.left, sum-node.val) + dfs(node.right, sum-node.val) + (sum == node.val) if node else 0

  return dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum) if root else 0

  解法二,用非递归后序遍历的框架,stack存储所有父结点,sums列表存储的是以任一结点为起始的路径和(有点类似动态规划?),因此sums的长度和stack一致,当sums中的任一数字与sum相等,都是一个满足要求的路径。在后序遍历的过程中,结点退栈,sums中对应的也退栈,并且每个数字减去该结点的值。该方法速度500ms,但是空间复杂度基本是top,beat 99.9%。

  class Solution:

  def pathSum(self, root: TreeNode, sum: int) -> int:

  if not root:

  return 0

  stack = []

  sums = []

  f = 0

  res = 0

  p = root

  while True:

  while p:

  stack.append(p)

  sums.append(0)

  for i in range(len(sums)):

  sums[i] += p.val

  if sums[i] == sum:

  res += 1

  p = p.left

  pre = None

  f = 1

  while stack and f:

  p = stack[-1]

  if p.right == pre:

  sums.pop()

  for i in range(len(sums)):

  sums[i] -= p.val

  stack.pop()

  pre = p

  else:

  p = p.right

  f = 0

  if not stack:

  break

  return res

  明显时间复杂度上还有很多优化空间,我们看解法三,大佬所做,52ms,可谓相当可以了。细细揣摩,大思路上,同上一个解法,仍然是只遍历一次,避免重复,因此需要存储曾出现的路径和,这一解法引入了hashmap。鄙人的方法慢在sums列表的值,需要挨个加减以维持其作用,而sumMap作用相同,通过操作字典的键值对,解决了性能问题。参考这一思路,可以在上面非递归的框架下改写一番。

  class Solution:

  def pathSum(self, root: TreeNode, sum: int) -> int:

  """

  :type root: TreeNode

  :type sum: int

  :rtype: int

  """

  from collections import defaultdict

  def helper(cur, sumSoFar):

  nonlocal res, sumMap

  sumSoFar += cur.val

  if sumSoFar == sum:

  res += 1 无锡看妇科的医院 http://www.ytsg120.cn

  res += sumMap[sumSoFar - sum]

  sumMap[sumSoFar] += 1

  if cur.left:

  helper(cur.left, sumSoFar)

  if cur.right:

  helper(cur.right, sumSoFar)

  sumMap[sumSoFar] -= 1

  if not root:

  return 0

  sumMap = defaultdict(int)

  res = 0 if root.val != sum else 1

  sumMap[root.val] = 1

  if root.left:

  helper(root.left, root.val)

  if root.right:

  helper(root.right, root.val)

  return res

  124. Binary Tree Maximum Path Sum

  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

  题目解析:

  这道题在我看来,似乎是路径题目中的大boss。题目百思不得其解,最后还是看了其他人的写法,自己琢磨了一番,其实不同于其他路径问题。我们先看代码。

  class Solution:

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

  max_sum = float("-inf")

  def helper(node):

  nonlocal max_sum

  if not node:

  return 0

  lt_sum = helper(node.left)

  rt_sum = helper(node.right)

  local_sum = max(node.val, max(lt_sum, rt_sum) + node.val) # 1

  max_sum = max(max_sum, max(local_sum, lt_sum + rt_sum + node.val)) # 2

  return local_sum

  helper(root)

  return max_sum

  首先,该题目的路径大有不同,不一定包括叶子结点,也不一定包括根结点,有可能是从左子到父到右子的路径。题目的结果,是一个全局变量;解题过程是一个普通的先序遍历,递归的过程中完成两件事:一是返回local_sum,是左或右子树最大和,代码1判断是该结点值自己最大,还是加上其左右子树之一的和最大(只能选一个),该局部值向上递归,相当于在求路径和的问题时,把这样的大问题分解为一个个小问题来解决;第二件事是更新max_sum,此时允许该结点值加上左右子树的最大和,构成一个完整的路径,判断改值是不是最大。


上一篇:Python3解leetcode Reach a Number


下一篇:阿里云全球交付中心正式成立,打造一流的全球服务能力