[数据结构与算法]leetcode 437. 路径总和 III

leetcode 437. 路径总和 III

题目链接

暴力双搜

复杂度 O(n^2)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    int dfs(TreeNode* root,int q)
        {
            if(!root)return 0;
            int res=0;
            if(root->val==q)res++;
            res+=dfs(root->left,q-root->val);
            res+=dfs(root->right,q-root->val);
            return res;
        }
    int pathSum(TreeNode* root, int q) {
        if(!root)return 0;
        int res=dfs(root,q);
        res+=pathSum(root->left,q);
        res+=pathSum(root->right,q);
        return res;
    }
};

哈希表+前缀和+dfs

复杂度O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int>hash;
    int res=0;
    int dfs(TreeNode* root,int q,int cur){
        if(!root)return 0;
        cur+=root->val;
        res+=hash[cur-q];
        hash[cur]++;  
        dfs(root->left,q,cur);
        dfs(root->right,q,cur);
        hash[cur]--;
        return res;      
    }
    int pathSum(TreeNode* root, int q) {
        if(!root)return 0;
        hash[0]=1;
        dfs(root,q,0);
        return res;
    }
};

leetcode 113. 路径总和 II

题目链接

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;
    vector<vector<int>> pathSum(TreeNode* root, int q) {
        if(!root)return res;
        dfs(root,q);
        return res;
    }
    void dfs(TreeNode* root,int q)
    {
        path.push_back(root->val);
        if(!root->left&&!root->right)
        {
            if(root->val==q)res.push_back(path);
            return ;
        }

        if(root->left){dfs(root->left,q-root->val);path.pop_back();}
        if(root->right){dfs(root->right,q-root->val);path.pop_back();}
    }
};