用的dfs思想。。
func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
if root == nil {
return false
}
var tempArray = Array<TreeNode>()
tempArray.append(root!)
return dfs(0,root,&tempArray,targetSum)
}
func dfs(_ index:Int,_ tempNode:TreeNode?,_ tempArray: inout [TreeNode],_ targetSum:Int) -> Bool{
if tempNode?.left == nil && tempNode?.right == nil {
let sum = tempArray.reduce(0, {$0 + $1.val})
//说明找到了
if sum == targetSum {
return true
}
return false
}
var array = Array<TreeNode?>()
if tempNode?.left != nil {
array.append(tempNode?.left)
}
if tempNode?.right != nil {
array.append(tempNode?.right)
}
for node in array {
tempArray.append(node ?? TreeNode(0))
let find = dfs(index + 1,node,&tempArray,targetSum)
if find {
return true
}
tempArray.removeLast()
}
return false
}
优化。。 增加参数记录总和。不用再次遍历数组
func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
if root == nil {
return false
}
var tempArray = Array<TreeNode>()
tempArray.append(root!)
var sum = root!.val
return dfs(root,&tempArray,targetSum,&sum)
}
func dfs(_ tempNode:TreeNode?,_ tempArray: inout [TreeNode],_ targetSum:Int,_ sum:inout Int) -> Bool{
if tempNode?.left == nil && tempNode?.right == nil {
//说明找到了
if sum == targetSum {
return true
}
return false
}
var array = Array<TreeNode?>()
if tempNode?.left != nil {
array.append(tempNode?.left)
}
if tempNode?.right != nil {
array.append(tempNode?.right)
}
for node in array {
tempArray.append(node ?? TreeNode(0))
sum += node!.val
let find = dfs(node,&tempArray,targetSum,&sum)
if find {
return true
}
sum -= tempArray.removeLast().val
}
return false
}
受到113启发再次优化。。不用存节点，直接存值
func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
if root == nil {
return false
}
var tempArray = Array<Int>()
var sum = root!.val
tempArray.append(sum)
return dfs(root,&tempArray,targetSum,&sum)
}
func dfs(_ tempNode:TreeNode?,_ tempArray: inout [Int],_ targetSum:Int,_ sum:inout Int) -> Bool{
if tempNode?.left == nil && tempNode?.right == nil {
//说明找到了
if sum == targetSum {
return true
}
return false
}
var array = Array<TreeNode?>()
if tempNode?.left != nil {
array.append(tempNode?.left)
}
if tempNode?.right != nil {
array.append(tempNode?.right)
}
for node in array {
tempArray.append(node!.val)
sum += node!.val
let find = dfs(node,&tempArray,targetSum,&sum)
if find {
return true
}
sum -= tempArray.removeLast()
}
return false
}
网友评论