二叉树路径和相关

发表于 | 分类于 ， ， |

二叉树路径和相关

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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    //递归
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil && 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();
    }
};
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
26
27
28
func pathSum(root *TreeNode, targetSum int) [][]int {
    res := [][]int{}
    temp := []int{}
    sum := 0
    
    var dfs func(*TreeNode, int)
    dfs = func(root *TreeNode, targetSum int) {
        //结束条件
        if root == nil {
            return
        }
        
        temp = append(temp, root.Val)
        sum += root.Val
        if sum == targetSum && root.Left == nil && root.Right == nil {
            path := make([]int, len(temp))
            copy(path, temp)
            res = append(res, path)
        }
        dfs(root.Left, targetSum)
        dfs(root.Right, targetSum)
        sum -= root.Val
        temp = temp[:len(temp)-1]
    }
    
    dfs(root, targetSum)
    return res
}

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func pathSum(root *TreeNode, targetSum int) int {
    if root == nil {
        return 0
    }
    res := dfs(root, int64(targetSum))
    res += pathSum(root.Left, targetSum)
    res += pathSum(root.Right, targetSum)
    return res
}

func dfs(root *TreeNode, targetSum int64) int {
    if root == nil {
        return 0
    }
    
    res := 0
    if int64(root.Val) == targetSum {
        res++
    }
    res += dfs(root.Left, targetSum-int64(root.Val))
    res += dfs(root.Right, targetSum-int64(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);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func sumNumbers(root *TreeNode) int {
    var dfs func(*TreeNode, int) int
    dfs = func(root *TreeNode, prevSum int) int {
        if root == nil {
            return 0
        }
        sum := prevSum*10 + root.Val
        if root.Left == nil && root.Right == nil {
            return sum
        } else {
            return dfs(root.Left, sum) + dfs(root.Right, sum)
        }
    }
    return dfs(root, 0)
}

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);
    }
};
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
26
27
28
29
30
31
32
33
34
func maxPathSum(root *TreeNode) int {
    res := math.MinInt32
    
    var dfs func(*TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        leftVal := max(dfs(root.Left), 0)
        rightVal := max(dfs(root.Right), 0)
        
        //节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        curVal := root.Val + leftVal + rightVal
        
        //更新答案
        res = max(curVal, res)
        
        // 返回节点的最大贡献值
        return root.Val + max(leftVal, rightVal)
    }
    
    dfs(root)
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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);
    }
};
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
26
27
28
29
30
31
32
33
34
func longestUnivaluePath(root *TreeNode) int {
    res := 0
    
    var dfs func(*TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        
        leftVal := dfs(root.Left)
        rightVal := dfs(root.Right)
        
        temp_left, temp_right := 0, 0
        if root.Left != nil && root.Left.Val == root.Val {
            temp_left += leftVal + 1
        }
        if root.Right != nil && root.Right.Val == root.Val {
            temp_right += rightVal + 1
        }
        res = max(res, temp_left+temp_right)
        
        return max(temp_left, temp_right)
    }
    
    dfs(root)
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func binaryTreePaths(root *TreeNode) []string {
    res := []string{}
    
    var dfs func(*TreeNode, string)
    dfs = func(root *TreeNode, s string) {
        if root == nil {
            return
        }
        
        s += strconv.Itoa(root.Val)
        
        if root.Left == nil && root.Right == nil {
            res = append(res, s)
        }
        
        s += "->"
        dfs(root.Left, s)
        dfs(root.Right, s)
    }
    
    dfs(root, "")
    return res
}
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;
    }
};
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
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
    var dfs func(*TreeNode, int) *TreeNode
    dfs = func(root *TreeNode, limit int) *TreeNode {
        left := root.Left
        right := root.Right
        if left == nil && right == nil {
            if root.Val >= limit {
                return root
            }
            return nil
        }
        limit -= root.Val
        if left != nil {
            root.Left = dfs(left, limit)
        }
        if right != nil {
            root.Right = dfs(right, limit)
        }
        if root.Left == nil && root.Right == nil {
            return nil
        }
        return root
    }
    return dfs(root, limit)
}
-------------本文结束 感谢阅读-------------
0%