一、问题描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:

给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         / \      \
        7   2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

二、方案一：递归

1、思路

递归地遍历每个节点，每遍历一个节点，从目标和中减去该节点的值。当到达叶子节点时，检查剩余的目标和是否为0。

2、代码实现

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

3、复杂度分析

• 时间复杂度：O(n)，其中n是树的节点数。每个节点只被访问一次。
• 空间复杂度：O(h)，其中h是树的高度。空间复杂度主要取决于递归栈的深度，而递归栈的深度等于树的高度。

三、方案二：迭代

1、思路

使用栈来迭代地遍历树。每个节点在栈中存储其路径和。当到达叶子节点时，检查路径和是否等于目标和。

2、代码实现

func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	stack := make([]*TreeNode, 0)
	stack = append(stack, root)

	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]

		if node.Left == nil && node.Right == nil && node.Val == targetSum {
			return true
		}

		if node.Right != nil {
			node.Right.Val += node.Val
			stack = append(stack, node.Right)
		}

		if node.Left != nil {
			node.Left.Val += node.Val
			stack = append(stack, node.Left)
		}
	}

	return false

	return false
}

3、复杂度分析

• 时间复杂度：O(n)，其中n是树的节点数。每个节点只被访问一次。
• 空间复杂度：O(n)，其中n是树的节点数。空间复杂度主要取决于栈的大小，栈的大小在最坏情况下会达到树的节点数。

四、总结

方案	时间复杂度	空间复杂度	备注
递归	O(n)	O(h)	递归实现简单，但空间复杂度取决于树的高度
迭代	O(n)	O(n)	迭代需要额外的空间来存储栈，但不受树的高度影响

递归和迭代两种方法各有优缺点，可以根据具体情况选择使用。