2020-05-05 437. Path Sum III Solution

ruicore · ruicore · commit 666dd84bfec5 · 2020-05-05T15:24:35.000+08:00
diff --git a/LeetCode/2020-05-01-437-Path-Sum-III.md b/LeetCode/2020-05-01-437-Path-Sum-III.md
@@ -0,0 +1,78 @@
+# LeetCode 437. Path Sum III
+
+## Description
+
+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:
+
+```py
+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
+```
+
+### 思路
+
+* 二叉树相关的题目很多情况下都需要用到递归来解决。
+* 根据题意，求使得和为给定数字的种树。不一定要求从根节点开始。
+* 思考递归这种解题方式时，需要将原问题拆解成更小的子问题，并且假设子问题已经解决。
+* 二叉树有左子树和右子树，我们假设左右子树的问题已经解决，即已经知道了左右子树可以形成满足条件的种数；那么此时还剩下以当前节点为起始节点可以形成的种数。
+* 即整颗二叉树可以形成的路径等于给定值的总数 = 必须以 node 节点为开始节点的种数 + node 左子树可以形成的路径数 + node 右子树可以形成的路径树。
+* 在求解以 node 节点开始的路径和为给定值的种数时候，可以使用 前/中/后 三种遍历方式中的任意一种。
+* 这里采用中序遍历的一种方式。
+
+
+```py
+# -*- coding: utf-8 -*-
+# @Author:             何睿
+# @Create Date:        2020-05-01 17:30:03
+# @Last Modified by:   何睿
+# @Last Modified time: 2020-05-01 19:54:16
+
+# Definition for a binary tree node.
+
+
+class TreeNode:
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+
+class Solution:
+    def pathSum(self, root: TreeNode, sum: int) -> int:
+        if not root:
+            return 0
+
+        return self.sumRoot(root, 0, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
+
+    def sumRoot(self, root, pre, sum_):
+
+        if not root:
+            return 0
+        pre += root.val
+
+        left = self.sumRoot(root.left, pre, sum_)
+        right = self.sumRoot(root.right, pre, sum_)
+
+        return (pre == sum_) + left + right
+```
