112. Path Sum

求二叉树根到叶结点路径的和是否等于一个给定的值

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        # 6 star， no idea, dfs, 必须掌握
        # todo, 必须掌握
        if not root:
            return False
        rs = self.dfs(root.val, root, sum)
        return True if rs else False


    def dfs(self, current, node , sum):
        if current == sum and not node.left and not node.right:
            return True
        if node:
            left = right = None
            if node.left:
                left = self.dfs(current+node.left.val, node.left, sum)
            if node.right:
                right = self.dfs(current+node.right.val, node.right, sum)
            # 左边或者右边的和等于sum了，则True
            if left or right:
                return True

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
func hasPathSum(root *TreeNode, sum int) bool {
	return checkSum(root, sum, 0)

}

func checkSum(node *TreeNode,  sum int, curSum int) bool {
	if node == nil {return false}
	curSum += node.Val
	if node.Left == nil && node.Right == nil && sum == curSum {
		return true
	}
	return checkSum(node.Left, sum, curSum) || checkSum(node.Right, sum, curSum)
}