{"id":9973,"date":"2023-03-05T07:51:10","date_gmt":"2023-03-05T15:51:10","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9973"},"modified":"2023-03-05T07:52:24","modified_gmt":"2023-03-05T15:52:24","slug":"leetcode-2583-kth-largest-sum-in-a-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-2583-kth-largest-sum-in-a-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2583. Kth Largest Sum in a Binary Tree"},"content":{"rendered":"\n

You are given the root<\/code> of a binary tree and a positive integer k<\/code>.<\/p>\n\n\n\n

The level sum<\/strong> in the tree is the sum of the values of the nodes that are on the same<\/strong> level.<\/p>\n\n\n\n

Return the <\/em>kth<\/sup><\/code> largest<\/strong> level sum in the tree (not necessarily distinct)<\/em>. If there are fewer than k<\/code> levels in the tree, return -1<\/code>.<\/p>\n\n\n\n

Note<\/strong> that two nodes are on the same level if they have the same distance from the root.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> root = [5,8,9,2,1,3,7,4,6], k = 2\nOutput:<\/strong> 13\nExplanation:<\/strong> The level sums are the following:\n- Level 1: 5.\n- Level 2: 8 + 9 = 17.\n- Level 3: 2 + 1 + 3 + 7 = 13.\n- Level 4: 4 + 6 = 10.\nThe 2nd<\/sup> largest level sum is 13.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> root = [1,2,null,3], k = 1\nOutput:<\/strong> 3\nExplanation:<\/strong> The largest level sum is 3.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • The number of nodes in the tree is n<\/code>.<\/li>
  • 2 <= n <= 105<\/sup><\/code><\/li>
  • 1 <= Node.val <= 106<\/sup><\/code><\/li>
  • 1 <= k <= n<\/code><\/li><\/ul>\n\n\n\n
    Solution: DFS + Sorting<\/strong><\/h2>\n\n\n\n
    Use DFS to traverse the tree and accumulate level sum. Once done, sort the level sums and find the k-th largest one.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    Note: sum can be very large, use long long.<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  long long kthLargestLevelSum(TreeNode* root, int k) {\n    vector sums;\n    function dfs = [&](TreeNode* root, int d) {\n      if (!root) return;\n      while (d >= sums.size()) sums.push_back(0);\n      sums[d] += root->val;\n      dfs(root->left, d + 1);\n      dfs(root->right, d + 1);\n    };\n    dfs(root, 0);\n    if (sums.size() < k) return -1;\n    sort(rbegin(sums), rend(sums));\n    return sums[k - 1];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given the root of a binary tree and a positive integer k. The level sum in the tree is the sum of the values of the nodes that…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[33,177,15,28],"class_list":["post-9973","post","type-post","status-publish","format-standard","hentry","category-tree","tag-dfs","tag-medium","tag-sorting","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9973","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9973"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9973\/revisions"}],"predecessor-version":[{"id":9975,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9973\/revisions\/9975"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9973"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9973"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}