[LeetCode] 703. Kth Largest Element in a Stream, Easy

1. 문제

• 정수 배열과 k가 주어질 때, add 후 k 번째로 큰 숫자를 반환하는 클래스를 작성하라.

2. 해결

class TreeCountNode {
    cnt: number;
    val: number;
    left: TreeCountNode | null;
    right: TreeCountNode | null;
    constructor(val:number, left?: TreeCountNode | null, right?: TreeCountNode | null) {
        this.cnt = 1;
        this.val = val;
        this.left = left || null;
        this.right = right || null;
    }
}

class KthLargest {
    k: number;
    root: TreeCountNode | null;
    constructor(k: number, nums: number[]) {
        this.k = k;
        
        for(const num of nums) {
            this.root = this.insert(this.root, num)     
        }
    }

    insert(node: TreeCountNode | null, value: number):TreeCountNode | null {
        if(!node) return new TreeCountNode(value);
        
        node.cnt++;

        if (value < node.val) {
            node.left = this.insert(node.left, value);
        } else {
            node.right = this.insert(node.right, value);
        }


        return node;
    }

    add(val: number): number {
        this.root = this.insert(this.root, val);
        return this.findKth(this.root, this.k);
    }

    findKth(node: TreeCountNode | null, k:number):number {
        if(!node) return -1;

        const rightCount = node.right ? node.right.cnt : 0;

        if(k <= rightCount) {
            return this.findKth(node.right, k);
        } else if(k === rightCount + 1) {
            return node.val;
        } else {
            return this.findKth(node.left, k - rightCount -1);
        }

    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */

• 노드에 cnt라는 필드를 통해 서브 트리에 존재하는 노드의 수를 저장.
• 입력받은 배열로 BST를 구성, 오른쪽 -> 자신 -> 왼쪽 순으로 탐색하면서 큰 수를 찾는다.
• 못풀었다. 다른 풀이 참고.