二叉树路径和相关

发表于 | 分类于 ， ， |

二叉树路径和相关

112.路径总和 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
    bool hasPathSum(TreeNode* root, int targetSum) {
        //递归
        if(root==nullptr) return false;
        if(root->left==nullptr && root->right==nullptr && root->val==targetSum) 
            return true;

        return hasPathSum(root->left, targetSum-root->val) || 
            hasPathSum(root->right, targetSum-root->val);
    }
};

113.路径总和 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    int sum=0;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }
    void dfs(TreeNode* root, int targetSum){
        //结束条件
        if(root==nullptr) return;
        
        temp.push_back(root->val);
        sum += root->val;
        if(sum==targetSum && root->left==nullptr && root->right==nullptr){
            res.push_back(temp);
        }
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
        sum -= root->val;
        temp.pop_back();
    }
};

437.路径总和 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return 0;
        int res = dfs(root, targetSum);
        res += pathSum(root->left, targetSum);
        res += pathSum(root->right, targetSum);
        return res;
    }

    int dfs(TreeNode* root, long long targetSum){
        if(root==nullptr) return 0;

        int res=0;
        if(root->val==targetSum){
            res++;
        }
        res += dfs(root->left, targetSum-root->val);
        res += dfs(root->right, targetSum-root->val);
        return res;
    }
};

129. 求根节点到叶子节点数字之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
    int dfs(TreeNode* root, int prevSum){
        if(root==nullptr) return 0;
        int sum = prevSum*10 + root->val;
        if(root->left==nullptr && root->right==nullptr){
            return sum;
        }else{
            return dfs(root->left, sum)+dfs(root->right, sum);
        }
    }
};

124.二叉树中的最大路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }
    int res=INT_MIN;
    int dfs(TreeNode* root){
        if(root==nullptr) return 0;

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftVal = max(dfs(root->left), 0);
        int rightVal = max(dfs(root->right), 0);

        //节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int curVal = root->val+leftVal+rightVal;

        //更新答案
        res = max(curVal, res);
        
        // 返回节点的最大贡献值
        return root->val + max(leftVal, rightVal);
    }
};

687.最长同值路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        dfs(root);
        return res;
    }
    int res=0;
    int dfs(TreeNode* root){
        if(root==nullptr) return 0;

        int leftVal = dfs(root->left);
        int rightVal = dfs(root->right);

        int temp_left=0, temp_right=0;
        if(root->left!=nullptr && root->left->val==root->val){
            temp_left += leftVal+1;
        }
        if(root->right!=nullptr && root->right->val==root->val){
            temp_right += rightVal+1;
        }
        res = max(res, temp_left+temp_right);

        return max(temp_left, temp_right);
    }
};

257.二叉树的所有路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> res;
    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root, "");
        return res;
    }
    void dfs(TreeNode* root, string s){
        if(root==nullptr) return ;

        s +=to_string(root->val);

        if(root->left==nullptr && root->right==nullptr){
            res.push_back(s);
        }
        
        s +="->";
        dfs(root->left, s);
        dfs(root->right, s);
    }
};
1080.根到叶路径上的不足节点

给定一棵二叉树的根 root，请你考虑它所有 从根到叶的路径：从根到任何叶的路径。（所谓一个叶子节点，就是一个没有子节点的节点）

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为「不足节点」，需要被删除。

请你删除所有不足节点，并返回生成的二叉树的根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        return dfs(root, limit);
    }
    TreeNode* dfs(TreeNode* root, int limit){
        TreeNode* left=root->left;
        TreeNode* right=root->right;
        if(left==nullptr && right==nullptr){
            return root->val >= limit ? root : nullptr;
        }
        limit -= root->val;
        if(left!=nullptr){
            root->left=dfs(left, limit);
        }
        if(right!=nullptr){
            root->right=dfs(right, limit);
        }
        if(root->left==nullptr&&root->right==nullptr){
            return nullptr;
        }
        return root;
    }
};
-------------本文结束 感谢阅读-------------
0%