爆刷leetcode——二叉树（二）——路径问题（一）

---

路径问题的分类

问题分类：
路径问题大致可以分为两种:
一、自顶向下： 从某一个节点开始（不一定是根节点），从上到下开始寻找路径，直到某一个节点（不一定是叶子节点）结束，这个问题与第二个问题相比，它的路径是不可拐弯的（也就是路径不能是左子树->自身->右子树）； 在leetcode上的题目有：
257. 二叉树的所有路径
面试题 04.12. 求和路径
112. 路径总和
113. 路径总和 II
437. 路径总和 III
988. 从叶结点开始的最小字符串

二、非自顶向下： 从任意节点到另一任意节点的路径，不需要自定向下，该路径是可以拐弯的；在leetcode上的题目有：
124. 二叉树中的最大路径和
687. 最长同值路径
543. 二叉树的直径

自顶向下问题

112. 路径总和

思路：
题目已经明确规定该路径必须是从根节点到叶子节点，所以我们只需要判断当到达叶子节点后targetSum能否等于0即可；我们利用dfs即可完成操作；

bool dfs(struct TreeNode* root, int targetSum)
{
   
    if(root == NULL)
        return false;

    //先减去当前节点的值
    targetSum -= root->val;

    //如果到达叶子节点，并且targetSum等于0
    if(root->left == NULL && root->right == NULL && targetSum == 0)
        return true;
        
	//左子树或右子树存在该路径皆可
    return dfs(root->left,targetSum) || dfs(root->right,targetSum)
1
2
3
4
5
6
7
8
9
10
11
12
13
14