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

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

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

解答:看到所有字眼,立即思考双递归,其中一个递归遍历所有节点,一个递归求解逻辑。根据题意路径只能是父亲往下,则往下找就ok,但需要注意一个问题就是一般问题写习惯了找到以后习惯性return,而这题不能return,因为可能两条路径某些节点完全重合,即该条路径终点如果不是叶子节点,则继续往下可能还有满足条件的路径。时间复杂度O(n^2),空间复杂度O(1)。
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    int res=0;
    int FindPath(TreeNode* rootint sum) {
        // write code here
        if(root==NULL)return 0;
        dfs(root,sum);
        return res;
    }
    void dfs(TreeNode* root,int tar){
        if(root==NULL)return;
        dfs_in(root,0,tar);
        dfs(root->left,tar);
        dfs(root->right,tar);
    }
    void dfs_in(TreeNode* root,int k,int tar){
        if(root==NULL)return;
        k=k+root->val;
        if(k==tar){
            res++;
        }
        dfs_in(root->left,k,tar);
        dfs_in(root->right,k,tar);
    }
};

全部评论

相关推荐

06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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