2019-11-20 155 views 评论

Leetcode题目解析（191120）：124&128

Leetcode 124：二叉树中的最大路径和

题目描述

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

解题思路

参见：
https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/

代码实现

int maxSum(TreeNode* root,int &amp;maxs)
{
    if (root == nullptr)
        return INT_MIN;
    int left = max(maxSum(root-&gt;left,maxs),0);
    int right = max(maxSum(root-&gt;right,maxs),0);
    int lmr = root-&gt;val + left + right;
    maxs = max(maxs, lmr);
    return root-&gt;val+max(left,right);
}
int maxPathSum(TreeNode* root) {
    if (root == nullptr)
        return 0;
    int maxs = INT_MIN;
    maxSum(root,maxs);
    return maxs;
}

int maxSum(TreeNode* root,int &maxs)

{

if (root == nullptr)

return INT_MIN;

int left = max(maxSum(root->left,maxs),0);

int right = max(maxSum(root->right,maxs),0);

int lmr = root->val + left + right;

maxs = max(maxs, lmr);

return root->val+max(left,right);

}

int maxPathSum(TreeNode* root) {

if (root == nullptr)

return 0;

int maxs = INT_MIN;

maxSum(root,maxs);

return maxs;

}

复杂度

运行时间

Leetcode 128：最长连续序列

题目描述

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

示例

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

代码实现

int longestConsecutive(vector&lt;int&gt;&amp; nums) {
    unordered_map&lt;int, int&gt;slen;
    int maxl = 0;
    for (auto num : nums) {
        if (slen[num] == 0)
        {
            int l = slen[num - 1], r = slen[num + 1];
            slen[num] = l + r + 1;
            slen[num + r] = l + r + 1;
            slen[num - l] = l + r + 1;
            maxl = maxl &gt; slen[num]? maxl : slen[num];
        }
    }
    return maxl;
}