题解 | 二叉树中和为某一值的路径(三)

二叉树中和为某一值的路径(三)

http://www.nowcoder.com/practice/965fef32cae14a17a8e86c76ffe3131f

这题首先需要遍历一遍树,把当前遍历的节点作为根节点出发,再去求符合条件的路径的个数。 第一次遍历可以用简单的层次遍历,利用队列实现;第二次遍历可以用dfs

方法一:非递归的dfs

/**
 * 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 FindPath(TreeNode* root, int sum) {
        // write code here
        if(!root)
            return 0;
        queue<TreeNode*> q;
        int count = 0;
        q.push(root);
        while(!q.empty()){//根节点层次遍历
            TreeNode* r =  q.front();
            count += dfs(r, sum);
            if(r->left)
                q.push(r->left);
            if(r->right)
                q.push(r->right);
            q.pop();
        }
        return count;
    }
    
    int dfs(TreeNode* root, int sum){//返回当前root下满足要求的路径个数
        if(!root)
            return 0;
        int count = 0;
        vector<TreeNode*> s;
        TreeNode* r = root,* pre = NULL;
        while(r || !s.empty()){//后序遍历
            while(r){
                s.push_back(r);
                r = r->left;
            }
            r = s.back();
            if(r->right && r->right != pre)
                r = r->right;
            else{
                if(isTrue(s, sum))
                    count ++;
                pre = r;
                r = NULL;
                s.pop_back();
            }
        }
        return count;
    }
    
    bool isTrue(vector<TreeNode*> s, int sum){
        for(int i = 0; i < s.size(); i ++)
            sum -= s[i]->val;
        if(!sum)
            return true;
        return false;
    }
};

方法二:递归的dfs

注意:当找到一条路径时,若路径尾节点非叶节点,则还需继续拓展路径,因为可能出现节点值为0、两条路径的拼接等情况。

/**
 * 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 FindPath(TreeNode* root, int sum) {
        // write code here
        if(!root)
            return 0;
        queue<TreeNode*> q;
        int count = 0;
        q.push(root);
        while(!q.empty()){//根节点层次遍历
            TreeNode* r =  q.front();
            count += dfs(r, sum);
            if(r->left)
                q.push(r->left);
            if(r->right)
                q.push(r->right);
            q.pop();
        }
        return count;
    }
    
    int dfs(TreeNode* root, int sum){//返回当前root下满足要求的路径个数
        if(!root)
            return 0;
        if(root->val == sum)
            return 1 + dfs(root->left, 0) + dfs(root->right, 0);
        return dfs(root->left, sum - root->val) + dfs(root->right, sum - root->val);
    }
};
全部评论

相关推荐

frutiger:逆天,我家就安阳的,这hr咋能说3k的,你送外卖不比这工资高得多?还说大厂来的6k,打发叫花子的呢?这hr是怎么做到说昧良心的话的
找工作时遇到的神仙HR
点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务