2.(或许有时递归函数是万能的)树-相关题请优先使用语法层面的递归解题

• 我有1个大胆的结论：无论回溯、DFS、BFS、树，我们甚至可以直接不在乎他们是啥，我们就用纯的【实现1个递归函数】的思考方式去解决问题，可能比所谓的这些逻辑更顺畅！
• 此外，树这个数据结构，他天然就是递归的可视化表达（类似数学中的数形结合）

437. 路径总和 III【hot100】

使用：递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
    res := 0
    bt(&res, root, targetSum, 0, false)
    return res
}

// 坑的地方在于：连续性！
func bt(res *int, root *TreeNode, targetSum int, curSum int, lastIsSelect bool) {
    if root == nil {
        return
    }

    // 如果上一个节点选了，这个节点必须选，才能保持路径连续
    if lastIsSelect {
        // 必须选择当前节点以保持路径连续
        tmpSum := curSum + root.Val
        if tmpSum == targetSum {
            (*res)++
        }
        // 继续选择左右子节点（必须选以保持连续）
        bt(res, root.Left, targetSum, tmpSum, true)
        bt(res, root.Right, targetSum, tmpSum, true)
        // 这里不能跳过当前节点，因为会破坏路径连续性
    } else {
        // 上一个节点没选，我们可以选择当前节点开始新路径
        // 选择当前节点开始新路径
        tmpSum := root.Val
        if tmpSum == targetSum {
            (*res)++
        }
        // 继续选择左右子节点（形成连续路径）
        bt(res, root.Left, targetSum, tmpSum, true)
        bt(res, root.Right, targetSum, tmpSum, true)
        
        // 或者跳过当前节点，从子节点重新开始
        tmpSum = 0
        bt(res, root.Left, targetSum, tmpSum, false)
        bt(res, root.Right, targetSum, tmpSum, false)
    }
}