keep-practicing · zwfang · Jan 8, 2019 · Jan 8, 2019
diff --git a/README.md b/README.md
@@ -108,6 +108,7 @@ continually updating 😃.
 * [235. Lowest Common Ancestor of a Binary Search Tree](src/0235_lowest_common_ancestor_of_a_binary_search_tree/lcaoabst.go)&nbsp;&nbsp;&nbsp;*`binary tree;`*
 * [257. Binary Tree Paths](src/0257_binary_tree_paths/binary_tree_paths.go)&nbsp;&nbsp;&nbsp;*`binary tree`*
 * [404. Sum of Left Leaves](src/0404_sum_of_left_leaves/sum_of_left_leaves.go)&nbsp;&nbsp;&nbsp;*`binary tree`*
+* [437. Path Sum III](src/0437_path_sum_3/path_sum_3.go)&nbsp;&nbsp;&nbsp;*`binary tree`*
 
 ### Binary Search
 * [33. Search in Rotated Sorted Array](./src/0033_search_in_rotated_sorted_array/search_in_rotated_sorted_array.go)&nbsp;&nbsp;&nbsp;*`array;`*&nbsp;&nbsp;*`binary search`*

diff --git a/src/0437_path_sum_3/path_sum_3.go b/src/0437_path_sum_3/path_sum_3.go
@@ -0,0 +1,48 @@
+/*
+437. Path Sum III
+https://leetcode.com/problems/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.
+*/
+// 2019-01-08
+
+package ps3
+
+// TreeNode Definition for a binary tree node.
+type TreeNode struct {
+	Val   int
+	Left  *TreeNode
+	Right *TreeNode
+}
+
+// recursive
+// time complexity: O(n), where n is the nodes number of the tree.
+// space complexity: O(h), where h is the height of the tree.
+func pathSum(root *TreeNode, sum int) int {
+	if nil == root {
+		return 0
+	}
+	return findPath(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
+}
+
+func findPath(node *TreeNode, val int) int {
+	if node == nil {
+		return 0
+	}
+
+	res := 0
+	if val == node.Val {
+		res += 1
+	}
+
+	res += findPath(node.Left, val-node.Val)
+	res += findPath(node.Right, val-node.Val)
+	return res
+}
diff --git a/src/0437_path_sum_3/path_sum_3_test.go b/src/0437_path_sum_3/path_sum_3_test.go
@@ -0,0 +1,28 @@
+package ps3
+
+import "testing"
+
+func createBinaryTree(nums []int) *TreeNode {
+	return performCreate(nums, 0)
+}
+
+func performCreate(nums []int, index int) *TreeNode {
+	if index >= len(nums) {
+		return nil
+	}
+
+	tree := TreeNode{Val: nums[index]}
+	tree.Left = performCreate(nums, 2*index+1)
+	tree.Right = performCreate(nums, 2*index+2)
+	return &tree
+}
+
+func TestPathSum(t *testing.T) {
+	root := createBinaryTree([]int{10, 5, -3, 3, 2, 9, 11, 3, -2, 3, 1})
+	sum := 8
+	expected := 3
+
+	if res := pathSum(root, sum); res != expected {
+		t.Errorf("expected %d, got %d", expected, res)
+	}
+}
diff --git a/src/README.md b/src/README.md
@@ -89,6 +89,7 @@
 |0404|[404. Sum of Left Leaves](0404_sum_of_left_leaves/sum_of_left_leaves.go)|Easy|*`binary tree`*|
 |0416|[Partition Equal Subset Sum](./0416_partition_equal_subset_sum/partition_equal_subset_sum.go)|Medium|*`dp;`* *`0-1 knapsack problem`*|
 |0435|[Non-overlapping Intervals(dp solution)](./0435_non_overlapping_intervals/dp_solution.go)   <br/>[Non-overlapping Intervals(greedy solution)](./0435_non_overlapping_intervals/greedy_solution.go)|Medium|*`dp;`* *`0-1 knapsack problem`*|
+|0437|[437. Path Sum III](0437_path_sum_3/path_sum_3.go)|Easy|*`binary tree`*|
 |0438|[ Find All Anagrams in a String](./0438_all_anagrams_in_a_string/all_anagrams_in_a_string.go)|Easy|*`sliding window`*|
 |0447|[Number of Boomerangs](./0447_number_of_boomerangs/number_of_boomerangs.go)|Easy||
 |0454|[4Sum II](./0454_4sum2/4sum2.go)|Medium||