首页 > itarticle > l112 path sum

l112 path sum

admin 11月 13, 2020 0

题目描述

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / 
            4   8
           /   / 
          11  13  4
         /        
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

解题思路

使用深度遍历的方式进行解决。

Go实现

func (root *TreeNode, target int, sum int) bool{
    if root == nil {
        return false
    }
    sum += root.Val

    if root.Left==nil && root.Right==nil {
        if sum == target {
            return true
        }else{
            return false
        }
    }
    return travel(root.Left, target, sum) || travel(root.Right, target, sum)
}

func hasPathSum(root *TreeNode, sum int) bool {
    return travel(root, sum, 0)
}