美文网首页
leetcode--124--二叉树中的最大路径和

leetcode--124--二叉树中的最大路径和

作者: minningl | 来源:发表于2020-11-08 22:36 被阅读0次

    题目:
    给定一个非空二叉树,返回其最大路径和。

    本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

    示例 1:

    输入:[1,2,3]

       1
      / \
     2   3
    

    输出:6
    示例 2:

    输入:[-10,9,20,null,null,15,7]

    -10
    /
    9 20
    /
    15 7

    输出:42

    链接:https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

    思路:
    1、这道题采用二叉树的后序遍历。对于每一个节点,计算其左右子树单侧的最大路径和,通过其左右侧、当前节点的和与之前的最大路径和进行对比,找到当前节点下的最大路径和。上述过程通过递归进行完成

    Python代码

    import sys
    
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution(object):
    
        def __init__(self):
            self.ans = -1*sys.maxint-1
    
        def singlePathSum(self, root):
            if not root:
                return 0
            left = max(0, self.singlePathSum(root.left))
            right = max(0, self.singlePathSum(root.right))
            self.ans = max(self.ans, root.val+left+right)
            return root.val + max(left, right)  # 单侧下最大路径
    
    
        def maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.singlePathSum(root)
    
            return  self.ans
            
    

    C++ 代码:

    /**
     * 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 ans = INT_MIN;
    
        int singlePathSum(TreeNode* root){
            if (root==nullptr) {
                return 0;
            }
            int left = max(0, singlePathSum(root->left));
            int right = max(0, singlePathSum(root->right));
            ans = max(ans, root->val+left+right);
            return root->val+max(left, right);
        }
    
        int maxPathSum(TreeNode* root) {
            singlePathSum(root);
            return ans;
        }
    };
    

    相关文章

      网友评论

          本文标题:leetcode--124--二叉树中的最大路径和

          本文链接:https://www.haomeiwen.com/subject/orkkbktx.html