Apes Together Strong.

https://leetcode.com/problems/kth-largest-element-in-a-stream/description/정수형 입력 데이터가 주어질 때, k 번째로 큰 값을 반환하도록 하라. 조금 함정이 있는 문제다. 데이터가 얼마나 있는지, 다른 데이터는 무엇인지, 사실 문제는 관심없다. 오로지 반환으로 원하는 것은 k 번째 큰 값이다.  우선 map 등의 정렬된 hash등으로 값을 가질 수 있다.모든 값이 보존되며, add 시 정렬로 인해, O(logN) 시간이 소요 된다. 하지만 검색 시도 O(logN)이 소요된다. ( O(1) 을 원하면 hash_map 을 써야 하지만, 정렬이 지원되지 않는다. )이것으로도 충분히 문제는 풀릴 것이다.  다음으로 priority queue를 생각해 볼..

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ Preorder와 Inorder traverse  정보가 주어질 때, 전체 tree를 구성하라. 우선 InOrder와 PreOrder에 대해 다시 정리할 필요가 있다.  DFS 그 순서 그대로 tree를 접근한다면, PreOrder 방식이라고 할 수 있다.어느 노드의 child를 어떤 식으로 attach하는지 정보를 얻기 위해 InOrder가 필요하다. inOrder는 이 값들을 tree의 밸런스 정보와 함께 가지고 있다. 즉, 특정 값이 inOrder에 존재 한다면, inOrder에서 해당 값보다 작은 index는 왼쪽 트리..

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/ 주어진 tree에서 k 번째로 작은 값을 찾아 반환하라.  2진트리에서 InOrder traverse가 기본적으로 정렬을 의미함을 이해 한다.  따라서 InOrder traverse했을 때, k 번째로 접근하는 node 값을 찾으면 된다.  코드 더보기bool kthSmallestInOrder(TreeNode* node, int& k, int& outValue){ if (node == nullptr) return false; if (kthSmallestInOrder(node->left, k, outValue)) return true; ..