has_path_sum

  • 2022-12-14
  • 浏览 (530)

has_path_sum.go 源码

package leetcode

// 路径总和

func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	if root.Left == nil && root.Right == nil {
		return targetSum == root.Val
	}
	return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}

// 广度优先搜索
func hasPathSum2(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	queue := []*TreeNode{root}
	queueVal := []int{root.Val}
	for len(queue) > 0 {
		node, val := queue[0], queueVal[0]
		queue, queueVal = queue[1:], queueVal[1:]
		if node.Left == nil && node.Right == nil {
			if val == targetSum {
				return true
			}
		}
		if node.Left != nil {
			queue = append(queue, node.Left)
			queueVal = append(queueVal, node.Left.Val+val)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
			queueVal = append(queueVal, node.Right.Val+val)
		}
	}
	return false
}

你可能感兴趣的文章

binary_tree_inorder_traversal

binary_tree_level_order_traversal

binary_tree_postorder_traversal

0  赞