题目描述

描述
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
数据范围：
1.树上的节点数满足 0 ≤n≤10000
2.每 个节点的值都满足 ∣val≤1000

例如：
给出如下的二叉树， sum=22

返回true，因为存在一条路径25→4→11→2的节点值之和为 22

** 题解1：先序遍历，自递归**

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        //递归出口
        if(!root) return false;
        sum-=root->val;
        if(sum ==0 && !root->left && !root->right)
            return true;
        return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
    }
};

** 题解2：非自递归**

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool dfs(TreeNode * root, int sum){
        if(!root) return false;//若走到空节点，说明没有对应路径，返回空
        sum-=root->val;
        if(!root->left && !root->right && sum==0)
            return true;
        return dfs(root->left,sum) || dfs(root->right, sum);
    }

    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        //递归出口
        if(!root) return false;
        return dfs(root, sum);
    }
};

题目描述：二叉树中和为某一值的路径（二）

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22

则合法路径有[[10,5,7],[10,12]]

分析：该题和路径（一）中的不同点在于该题不仅仅要找到所有路径，还要将所有的路径存入数组中。

题解：先序遍历，递归

代码

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void dfs(TreeNode* root,int expectNumber,vector<int> &path,vector<vector<int>> &pathrsult){
        if(!root) return;
        path.push_back(root->val);
        expectNumber-=root->val;
        if(expectNumber ==0 && !root->left && !root->right){
            pathrsult.push_back(path);//满足条件，就把数组放置在结果数组中
        }
        dfs(root->left,expectNumber,path,pathrsult);
        dfs(root->right,expectNumber,path,pathrsult);
        //如果左子树和右子树全部遍历了，
        //expectNumber!=0，那么回溯，同时path最后一个元素弹出
        path.pop_back();
    }

    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
//         由于本题目不是二叉树两个节点之间的比较，且DFS递归的入口就是根节点
//         采用深度优先的算法，只有先序遍历满足题目条件
        vector<vector<int>> pathrsult;
        vector<int> path;
        //递归出口
        if(!root) return pathrsult;
        dfs(root,expectNumber,path,pathrsult);
        return pathrsult;
    }
};

题目描述：二叉树中和为某一值的路径（三）

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于2^31-1)

假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    int result = 0;//结果作为全局变量
    void dfs(TreeNode* root, int sum){
        if(!root) return;
        sum-=root->val;
        if(sum == 0){
            result++;//注意：这里之后不能返回
        }
        dfs(root->left,sum);
        dfs(root->right,sum);
    }

    int FindPath(TreeNode* root, int sum) {
        // write code here
        //注意：本体不能采用路径（二）的方法，采用路径（二）查找的是从根节点到叶子节点的路径
        //使用vector保存路径。对于本体来说，由于没有上述条件，vector保存很可能超出内存限制
        if(!root) return result;
        dfs(root,sum);//先从根节点开始进行遍历
        FindPath(root->left,sum);//再遍历左子树
        FindPath(root->right,sum);//最后遍历右子树
        return result;
    }
};