Apes Together Strong.

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/ 주어진 트리에서 두개의 target 노드 중, 가장 낮은 위치의 공통 부모 노드를 찾아라. 특정 노드간의 경로를 우선 기록한다. 그리고 두 노드 경로를 비교해서 달라지기 시작하면, 그 바로 직전 노드가 가장 낮은 공통 부모다.  코드.더보기bool collectPathToNode(TreeNode* node, TreeNode* target, vector& vBuff){ if (node == nullptr) return false; vBuff.push_back(node); if (node == target) ..

https://leetcode.com/problems/subtree-of-another-tree/description/ 주어진 두개의 tree가 있을 때, 하나의 트리중 일부가 다른 트리와 동일한지 판단하라. 모든 노드에 대해 subRoot tree와 같은지 비교하면 될 것이다.  이러면 두번 돌게 되는데...  단일 pass에 모두 처리하는 방법에 대해 고민 필요. 코드. 더보기void isSameTreeHelper(TreeNode* nodeA, TreeNode* nodeB, bool& same){ if (!same) return; if (nodeA == nullptr && nodeB == nullptr) return; if ((nodeA == nullptr && nod..

https://leetcode.com/problems/same-tree/description/ 주어진 두개의 트리가 동일한지 확인하라.  두 트리의 원소의 모든 값을 대조한다. 코드더보기void isSameTreeHelper(TreeNode* nodeA, TreeNode* nodeB, bool& same){ if(!same) return; if(nodeA==nullptr && nodeB==nullptr) return; if((nodeA==nullptr && nodeB!=nullptr) || (nodeA!=nullptr && nodeB==nullptr)) { same = false; return; } if(nodeA->val != n..

https://leetcode.com/problems/balanced-binary-tree/description/ 주어진 이진트리가 balanced binary tree인지 판단하라.  balanced 이진트리가 정확하게 무엇인지 먼저 재정의 해 보자. 특정 노드 기준으로 depth차가 최대 1이어야 한다. 다음 그림에서 dv 가  특정 노드에서 depth차를 의미한다.  아래 노드는 B 노드가 dv 2로 만족하지 않는다.  따라서 특정 노드에서 양 child 최대 depth를 구하고 그 차가 1보다 같거나 작은지 판단한다.  코드.더보기int isBalancedDFS(bool& isBalanced, TreeNode* node){ if (!isBalanced) return isBalan..

https://leetcode.com/problems/diameter-of-binary-tree/description/  주어진 tree의 최대 diameter 길이를 구하라.diameter란 두 leaf 노드 간 최대 거리를 말하며, 이는 root를 거치지 않을 수 있다. 특정 노드를 기준으로 left child와 right child의 max count가 diameter가 된다. 이 diameter를 모든 노드 기준으로 구하고, 그 중 max 값을 반환한다.  문제는 이 연산을 child count를 구하는 것과 (최적화를 위해) 동시에 처리해야 한다는 것이다.이것으로 Easy보다는 Medium에 가까운 문제.  코드 더보기int diameterOfBinaryTreeDFS(int& maxDiamete..

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ 주어진 binary tree의 최대 depth 를 구하라.  DFS 식으로 최대 depth를 카운팅 한다. 코드  int maxDepthDFS(TreeNode* node){ if (node == nullptr) return 0; int left = maxDepth(node->left) + 1; int right = maxDepth(node->right) + 1; return max(left, right);}int maxDepth(TreeNode* root) { return maxDepthDFS(root);}  결과

https://leetcode.com/problems/invert-binary-tree/description/ 주어진 binary tree를 그림과 같이 역전시켜라. 쉬워 보이지만, 접근을 잘 해야 하는 문제.  제일 하단 leaf 노드부터 뒤집으면 그 위로 차례로 뒤집으면 해결됨을 파악해야 한다. 각 depth 별로 노드를 얻어 하려고 하면 복잡해 지고, DFS방식으로 접근해서 하단부터 값을 얻고 위로 올라오면서 적용한다.  코드 TreeNode* invertTree(TreeNode* node){ if (node == nullptr) return nullptr; auto left = invertTree(node->left); auto right = invertTree(nod..

https://leetcode.com/problems/merge-k-sorted-lists/description/ 다수의 정렬된 list가 주어질 때, 모든 정렬을 유지하면서 이 list를 하나로 merge 하라. 정렬이 되어 있으므로, 각 list의 제일 앞 node를 비교하며 제일 작은 순서대로 새 노드에 연결하면 될 것이다.  매번 모든 앞 노드를 비교하면서 최소 값을 가진 노드를 찾을 수 있고, 이것은 시간이 많이 걸릴 것이다. 혹은 추가되는 노드만 더하면서 정렬할 수도 있겠다. map 이나 priority queue를 사용하면 될 것 같다.  코드 더보기void pushNode(map>& mNodes, ListNode* target){ if (mNodes.find(target->val) =..

https://leetcode.com/problems/lru-cache/description/ LRU Cache를 구현하라. LRU Cache 구현의 핵심은, list를 이용하여, 가장 최근에 사용한 데이터를 list의 제일 앞쪽에 위치시키고, 따라서 capacity가 꽉 차면 가장 마지막에 data를 삭제하는 것이다. 이때 데이터 접근에 따라 list에서 해당 데이터를 찾고 앞쪽에 위치시켜야 하는데, 이 검색시간을 O(1)로 하는게 문제 풀이의 핵심이라 할 수 있다.  결국 list의 iterator를 이용해 한번에 지워야 한다.  코드 더보기class LRUCache { int _capacity; list> _listData; // value, key. unor..

https://leetcode.com/problems/find-the-duplicate-number/description/ 아래와 같은 정수 배열이 주어질 때 단 하나의 중복 값이 존재한다. 이 값을 찾아라.  입력 배열을 수정하지 말고, 추가 메모리를 사용하지 말라. 이 문제가 linked list category인 이유가 있다. 따라서 해석이 중요한 문제다.  각 원소가 다음 원소의 index의 위치라고 한다면, 중복되는 값은 cycle의 시작 지점을 의미한다.  우선, cycle이 존재하는 지 판단하고, 그 지점을 찾는다.찾고 cycle의 시작점을 찾는다.  그러면 답이 찾아진다. 코드더보기int findDuplicate(vector& nums) { int idxFast = 0; int ..