{"id":10188,"date":"2024-10-12T22:02:58","date_gmt":"2024-10-13T05:02:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10188"},"modified":"2024-10-12T22:04:03","modified_gmt":"2024-10-13T05:04:03","slug":"leetcode-3319-k-th-largest-perfect-subtree-size-in-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-3319-k-th-largest-perfect-subtree-size-in-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode\u00a03319. K-th Largest Perfect Subtree Size in Binary Tree"},"content":{"rendered":"\n

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

Return an integer denoting the size of the kth<\/sup><\/code> largest <\/em>perfect binary<\/strong> <\/em><\/p>\n\n\n\n

subtree, or -1<\/code> if it doesn’t exist.<\/p>\n\n\n\n

A perfect binary tree<\/strong> is a tree where all leaves are on the same level, and every parent has two children.<\/p>\n\n\n\n

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

Input:<\/strong> root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2<\/p>\n\n\n\n

Output:<\/strong> 3<\/p>\n\n\n\n

Explanation:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1]<\/code>.
The 2nd<\/sup><\/code> largest size is 3.<\/p>\n\n\n\n

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

Input:<\/strong> root = [1,2,3,4,5,6,7], k = 1<\/p>\n\n\n\n

Output:<\/strong> 7<\/p>\n\n\n\n

Explanation:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]<\/code>. The size of the largest perfect binary subtree is 7.<\/p>\n\n\n\n

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

Input:<\/strong> root = [1,2,3,null,4], k = 3<\/p>\n\n\n\n

Output:<\/strong> -1<\/p>\n\n\n\n

Explanation:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

The sizes of the perfect binary subtrees in decreasing order are [1, 1]<\/code>. There are fewer than 3 perfect binary subtrees.<\/p>\n\n\n\n

Constraints:<\/strong><\/p>\n\n\n\n

  • The number of nodes in the tree is in the range\u00a0[1, 2000]<\/code>.<\/li>
  • 1 <= Node.val <= 2000<\/code><\/li>
  • 1 <= k <= 1024<\/code><\/li><\/ul>\n\n\n\n

    Solution: DFS<\/strong><\/h2>\n\n\n\n

    Write a function f() to return the perfect subtree size at node n.<\/p>\n\n\n\n

    def f(TreeNode n):
    if not n: return 0
    l, r = f(n.left), f(n.right)
    return l + r + 1 if l == r && l != -1 else -1<\/p>\n\n\n\n

    Time complexity: O(n + KlogK)
    Space complexity: O(n)<\/p>\n\n\n\n

    class Solution {\npublic:\n  int kthLargestPerfectSubtree(TreeNode* root, int k) {\n    vector<int> ss;\n    function<int(TreeNode*)> PerfectSubtree = [&](TreeNode* node) -> int {\n      if (node == nullptr) return 0;\n      int l = PerfectSubtree(node->left);\n      int r = PerfectSubtree(node->right);\n      if (l == r && l != -1) {\n        ss.push_back(l + r + 1);\n        return ss.back();\n      }\n      return -1;  \n    };\n    PerfectSubtree(root);\n    sort(rbegin(ss), rend(ss));\n    return k <= ss.size() ? ss[k - 1] : -1;\n  }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    You are given the root of a binary tree and an integer k. Return an integer denoting the size of the kth largest perfect binary  subtree, or -1 if it doesn’t exist. A perfect binary tree is…<\/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":[30,33,177,823,28],"class_list":["post-10188","post","type-post","status-publish","format-standard","hentry","category-tree","tag-binary-tree","tag-dfs","tag-medium","tag-perfect-tree","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10188","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=10188"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10188\/revisions"}],"predecessor-version":[{"id":10191,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10188\/revisions\/10191"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10188"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10188"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10188"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}