题目链接：LeetCode 112. 路径总和
题意：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
解题思路：
首先在使用递归法遍历二叉树时，要明确什么时候有返回值？什么时候不需要返回值？这里总结如下三点：
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
递归法
递归代码如下：
func hasPathSum(root *TreeNode, targetSum int) bool {
return dfs(root,targetSum)
}
func dfs(root *TreeNode,targetSum int)bool {
if root == nil {
return false
}
targetSum -= root.Val
if root.Left == nil && root.Right == nil && targetSum == 0{
return true
}
return dfs(root.Left,targetSum) || dfs(root.Right,targetSum)
}
迭代法
如果采用迭代法遍历二叉树，则在利用栈来存储各个节点的同时，也要存储根节点到该节点的路径上的数值总和
迭代法代码
class solution {
public:
bool haspathsum(TreeNode* root, int sum) {
if (root == null) return false;
// 此时栈里要放的是pair<节点指针，路径数值>
stack<pair<TreeNode*, int>> st;
st.push(pair<TreeNode*, int>(root, root->val));
while (!st.empty()) {
pair<TreeNode*, int> node = st.top();
st.pop();
// 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
if (!node.first->left && !node.first->right && sum == node.second) return true;
// 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
if (node.first->right) {
st.push(pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));
}
// 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
if (node.first->left) {
st.push(pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));
}
}
return false;
}
};