Skip to content

3319. K-th Largest Perfect Subtree Size in Binary Tree 👍

  • Time: $O(n + \texttt{sort})$
  • Space: $O(n)$
 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
struct T {
  bool isPerfect;
  int sz;
};

class Solution {
 public:
  int kthLargestPerfectSubtree(TreeNode* root, int k) {
    vector<int> ans;
    dfs(root, ans);
    ranges::sort(ans, greater<>());
    return ans.size() < k ? -1 : ans[k - 1];
  }

 private:
  T dfs(TreeNode* root, vector<int>& ans) {
    if (root == nullptr)
      return {true, 0};
    const auto l = dfs(root->left, ans);
    const auto r = dfs(root->right, ans);
    if (l.isPerfect && r.isPerfect && l.sz == r.sz) {
      const int sz = 1 + l.sz + r.sz;
      ans.push_back(sz);
      return {true, sz};
    }
    return {false, 0};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
record T(boolean isPerfect, int sz) {}

class Solution {
  public int kthLargestPerfectSubtree(TreeNode root, int k) {
    List<Integer> ans = new ArrayList<>();
    dfs(root, ans);
    Collections.sort(ans, Collections.reverseOrder());
    return ans.size() < k ? -1 : ans.get(k - 1);
  }

  private T dfs(TreeNode root, List<Integer> ans) {
    if (root == null)
      return new T(true, 0);
    T l = dfs(root.left, ans);
    T r = dfs(root.right, ans);
    if (l.isPerfect() && r.isPerfect() && l.sz() == r.sz()) {
      final int sz = 1 + l.sz() + r.sz();
      ans.add(sz);
      return new T(true, sz);
    }
    return new T(false, 0);
  }
}

 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
from dataclasses import dataclass


@dataclass(frozen=True)
class T:
  isPerfect: bool
  sz: int


class Solution:
  def kthLargestPerfectSubtree(self, root: TreeNode | None, k: int) -> int:
    ans = []
    self._dfs(root, ans)
    if len(ans) < k:
      return -1
    return sorted(ans, reverse=True)[k - 1]

  def _dfs(self, root: TreeNode, ans: list[int]) -> T:
    if not root:
      return T(True, 0)
    l = self._dfs(root.left, ans)
    r = self._dfs(root.right, ans)
    if l.isPerfect and r.isPerfect and l.sz == r.sz:
      sz = 1 + l.sz + r.sz
      ans.append(sz)
      return T(True, sz)
    return T(False, 0)