C语言重构【437】路径总和 III(2020-1024=996)

一时失言乱红尘 2022-12-18 00:55 110阅读 0赞

### 文章目录 ###

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

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

#### 题目 ####

给定一个二叉树，它的每个结点都存放着一个整数值。
    
    找出路径和等于给定数值的路径总数。
    
    路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
    
    二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
    
    示例：
    
    root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    
          10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1
    
    返回 3。和等于 8 的路径有:
    
    1.  5 -> 3
    2.  5 -> 2 -> 1
    3.  -3 -> 11

#### 方案： ####

/** * 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 jud,cnt=0;
        int pathSum(TreeNode* root, int sum) { 
            jud=sum;
            path1(root);
            return cnt;
        }
        void path1(TreeNode* root){ 
            if(root==NULL)return;
            //每次找该点到所有点的距离
            path2(root,0);
            path1(root->left);
            path1(root->right);
            return;
        }
        void path2(TreeNode* root,int len){ 
            if(root==NULL) return;
            int tmp=root->val+len;
            if(tmp==jud) cnt++;
            path2(root->left,tmp);
            path2(root->right,tmp);
            
        }
    };

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

*  时间复杂度：O(n^2)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode