LeetCode 3319: K-th Largest Perfect Subtree Size in Binary Tree

Explanation

To solve this problem, we can perform a postorder traversal of the binary tree. At each node, we recursively calculate the size of the subtree rooted at that node. For a subtree to be perfect, it must be a full binary tree, i.e., all internal nodes have exactly 2 children, and all leaves are at the same level. We can calculate the size of a subtree by recursively calculating the sizes of its left and right subtrees and checking if they are perfect and have the same size.

We maintain a priority queue to store the sizes of perfect subtrees in non-increasing order. Once we have collected all perfect subtree sizes, we can find the k-th largest size from the priority queue.

Space Complexity

The space complexity is O(n) for the priority queue and the recursive stack space.

Time Complexity

The time complexity of this approach is O(n^2) in the worst case, where n is the number of nodes in the binary tree.

class Solution {
    PriorityQueue<Integer> sizes = new PriorityQueue<>(Collections.reverseOrder());

    public int kthLargest(TreeNode root, int k) {
        postOrder(root);
        if (sizes.size() < k) return -1;
        while (k > 1) {
            sizes.poll();
            k--;
        }
        return sizes.poll();
    }

    private int postOrder(TreeNode node) {
        if (node == null) return 0;
        int left = postOrder(node.left);
        int right = postOrder(node.right);
        if (isPerfect(node, left, right)) {
            sizes.offer(left + right + 1);
        }
        return left + right + 1;
    }

    private boolean isPerfect(TreeNode node, int leftSize, int rightSize) {
        return (leftSize == 0 && rightSize == 0) || (leftSize == rightSize);
    }
}