力扣112. 路径总和（带讲解回溯过程和遇到的递归问题）

题目：

给你二叉树的根节点?root?和一个表示目标和的整数?targetSum?。判断该树中是否存在?根节点到叶子节点?的路径，这条路径上所有节点值相加等于目标和?targetSum?。如果存在，返回?true?；否则，返回?false?。

叶子节点?是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

• 树中节点的数目在范围?[0, 5000]?内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

思路：

本题递归法用前，中，后序方法都可以，因为不涉及中间节点的处理过程，本题需要一个计数器count来判断是否和目标值相同。把所有路径遍历一遍看是否有路径和目标值相同。

?本题主要涉及两个问题：

1. 回溯
2. 返回值

?有递归就有回溯，只不过平时写的代码都把回溯过程隐藏起来了，下面以本题代码为例讲解说明

if node.left:
    count -= node.left.val
    if self.traversal(node.left, count):
        return True
    count += node.left.val

上面是完整代码，把回溯过程完整的体现出来了

if node.left:
    if self.traversal(node.left, count - node.left.val):
        return True

?这个是简洁版代码，把回溯过程隐藏起来了，这段代码把count - node.left.val的值作为参数进行递归了，而没有改变count的值所以没有体现出回溯过程。

那么返回值呢？（结合完整代码部分来看，此处只放部分代码）

这个返回值困扰了我一段时间，正常写遍历时是这样的

        if node.left:
            count -= node.left.val
            self.traversal(node.left, count)
            count += node.left.val

?而在本题中却需要进行判断 如果是Ture则返回True，因为在调用递归时它是有返回值的（要么为True要么为False），所以再递归调用时得到的是bool类型的返回值，需要再进行一次判断。

        if node.left:
            count -= node.left.val
            if self.traversal(node.left, count):
                return True
            count += node.left.val

完整代码：

递归回溯法：

# 定义二叉树节点的类
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # 如果根节点为空，直接返回False
        if not root:
            return False
        # 调用traversal方法，传入根节点和目标和减去根节点值
        return self.traversal(root, targetSum - root.val)

    # 定义辅助函数traversal，用于深度优先搜索遍历二叉树
    def traversal(self, node, count):
        # 如果当前节点是叶子节点且count等于0，则返回True
        if not node.left and not node.right and count == 0:
            return True 
        # 如果当前节点是叶子节点但count不等于0，则返回False
        if not node.left and not node.right and count != 0:
            return False
        # 如果当前节点有左子节点
        if node.left:
            count -= node.left.val
            # 递归调用traversal方法，传入左子节点和更新后的count
            if self.traversal(node.left, count):
                return True
            count += node.left.val
        # 如果当前节点有右子节点
        if node.right:
            count -= node.right.val
            # 递归调用traversal方法，传入右子节点和更新后的count
            if self.traversal(node.right, count):
                return True
            count += node.right.val
        # 如果左右子节点都不满足条件，则返回False
        return False

迭代：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        # 此时栈里要放的是pair<节点指针，路径数值>
        st = [(root, root.val)]
        while st:
            node, path_sum = st.pop()
            # 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
            if not node.left and not node.right and path_sum == targetSum:
                return True
            # 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
            if node.right:
                st.append((node.right, path_sum + node.right.val))
            # 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
            if node.left:
                st.append((node.left, path_sum + node.left.val))
        return False