C语言重构【113】路径总和 II

左手的ㄟ右手 2022-12-02 01:17 123阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算
             *  杂记

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
    
    说明: 叶子节点是指没有子节点的节点。
    
    示例:
    给定如下二叉树，以及目标和 sum = 22，
    
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1
    返回:
    
    [
       [5,4,11,2],
       [5,8,4,5]
    ]

#### 方案： ####

*  用的C++

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        vector<vector<int>> ans;
        void DFS(TreeNode* root, vector<int>&t,int sum){ 
            if(root == nullptr) return;
            t.push_back(root->val);
            if(root->val == sum && root-> left == nullptr && root->right==nullptr)
            //叶子节点，且符合题目要求
                ans.push_back(t);
            DFS(root->left,t,sum-root->val);
            DFS(root->right,t,sum-root->val);
            t.pop_back();
        }
        vector<vector<int>> pathSum(TreeNode* root, int sum) { 
            vector<int> t;
            DFS(root,t,sum);
            return ans;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：最坏是这样的O(n\*2^(n-1))

#### 杂记 ####

*  突然发现C++和Java的复杂程度其实差不多，就做算法题来说
 *  [c/c++容器操作][c_c]

[Git]: https://github.com/ch98road/leetcode
[c_c]: https://www.cnblogs.com/spring-hailong/p/6109702.html