Add: Path Sum

openset · openset · commit 665d0a8601e4 · 2019-12-10T10:24:57.000+08:00
diff --git a/problems/path-sum/path_sum.go b/problems/path-sum/path_sum.go
@@ -1 +1,24 @@
 package problem112
+
+import "github.com/openset/leetcode/internal/kit"
+
+// TreeNode - Definition for a binary tree node.
+type TreeNode = kit.TreeNode
+
+/**
+ * Definition for a binary tree node.
+ * type TreeNode struct {
+ *     Val int
+ *     Left *TreeNode
+ *     Right *TreeNode
+ * }
+ */
+func hasPathSum(root *TreeNode, sum int) bool {
+	if root == nil {
+		return false
+	}
+	if root.Left == nil && root.Right == nil {
+		return root.Val == sum
+	}
+	return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
+}
diff --git a/problems/path-sum/path_sum_test.go b/problems/path-sum/path_sum_test.go
@@ -1 +1,29 @@
 package problem112
+
+import (
+	"testing"
+
+	"github.com/openset/leetcode/internal/kit"
+)
+
+type testType struct {
+	in   []int
+	sum  int
+	want bool
+}
+
+func TestHasPathSum(t *testing.T) {
+	tests := [...]testType{
+		{
+			in:   []int{5, 4, 8, 11, kit.NULL, 13, 4, 7, 2, kit.NULL, kit.NULL, kit.NULL, 1},
+			sum:  22,
+			want: true,
+		},
+	}
+	for _, tt := range tests {
+		got := hasPathSum(kit.SliceInt2TreeNode(tt.in), tt.sum)
+		if got != tt.want {
+			t.Fatalf("in: %v, got: %v, want: %v", tt.in, got, tt.want)
+		}
+	}
+}
