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

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
            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，此时允许该结点值加上左右子树的最大和，构成一个完整的路径，判断改值是不是最大。

路径的题目可以出的比较有难度，我们后续持续更新...