Apes Together Strong.

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description Q. 오름차순으로 정렬된 array가 주어질 때 이 array로 균형잡힌 binary tree를 구성하라. Solution. 이미 정렬이 되어 있으므로, 어느 지점을 기준으로 해도 작은 쪽 index 방향(left)은 작은값, 큰 index 방향(right)은 큰 값이 오게 된다. 다만 최대한 균형잡힌 기준으로 binary tree를 구성해야 하므로, 가운데를 기준으로 계속 partitioning 하며, 트리를 구성한다. 더보기 TreeNode* sortedArrayToBST_BT(vector& nums, int left, int right) { if(l..

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description Q. Preorder와 Inorder 순회 결과 배열로 tree를 구성하라.  Solution.  Tree 구성파트의 좋은 문제.  pre order는 self(mid), left, right 순서대로 traverse 하므로, tree를 해당 순서대로 visit 하는 그대로의 배열 결과가 된다.  따라서 depth first search 하면서 self, left, right를 배열 순서대로 값이 tree에 매칭하면 된다.   하지만 이것으로는 많은 다양한 트리가 만들어 질수 있으므로, 여기서 inorder traverse 정보..

https://leetcode.com/problems/maximum-depth-of-binary-tree/description Q. 해당 binary tree의 최대 depth 를 찾아라. Solution. 직관적으로 접근한다. Depth first로 tree를 traverse 하고, node가 valid 할 때까지 depth를 증가 시킨다. Tree는 left, right leafe가 있으므로, 둘 중 더 큰 depth만 위로 반환한다. 더보기 int maxDepth_BT(TreeNode* node, int maxDepth) { if (node == NULL) return maxDepth; int maxL = maxDepth_BT(node->left, maxDepth + 1); int maxR = ma..

https://leetcode.com/problems/binary-tree-level-order-traversal/description Q. 해당 tree를 level 별로 데이터를 만들어 반환하라. Solution. 특정 자료구조 문제를 풀기 위해서 반드시 알아야 하는 기본 접근법들이 있다. 이 문제는 binary tree의 그런 문제들 중 하나로, 반드시 풀이법을 알아둬야 하겠다. 더보기 vector levelOrder(TreeNode* root) { queue qBuff; vector vRet; if(root == NULL) return vRet; qBuff.push(root); while(!qBuff.empty()) { int size = qBuff.size(); vector vLevel; for..

https://leetcode.com/problems/symmetric-tree/description Q. root node를 기준으로 값이 mirror 되는 tree인지 여부를 반환하라. Solution. 직관적으로 해 본다. 같은 level의 tree node를 순서대로 모두 구한 후에 그 반을 기준으로 양 노드들을 비교 해 주면 될 것 같다. 동레벨의 노드를 얻기위해서는 queue를 사용하면 된다. 아이디어대로 코드를 만들어 본다. 더보기 bool isSymmetric(TreeNode* root) { queue qBuff; qBuff.push(root); while (!qBuff.empty()) { int size = qBuff.size(); vector vNodes; for (int q = 0; ..

https://leetcode.com/problems/validate-binary-search-tree/description Q. 입력된 tree가 유효한 binary search tree인지 판단하라.   Solution.  우선 Binary Search Tree의 요건에 대해 생각해 보자.  특정 노드 기준으로 left side가 모두 해당 노드 값보다 작아야 한다.  right side는 모두 커야 한다.   노드의 child가 하나 일 때는 비교적 간단하다.  위 트리로 다시 확인해 보자. 6의 노드의 지점에서 보자면 간단하다. 조건을 만족한다.  그러나 위 노드를 root, 즉 5노드의 지점에서 다시 보자. 이때는 left 전체의 최대값과, right 전체의 최소값을 해당 노드와 비교해야 한다...

https://leetcode.com/problems/binary-tree-inorder-traversal/description Q. 주어진 tree를 inorder로 순회하고 그 값을 반환하라. Solution. Binary Tree의 기본기. 가급적 풀 줄 알아야 하겠다. void inorderTraverseBT(vector& vOut, TreeNode* node) { if (node == NULL)return; inorderTraverseBT(vOut, node->left); vOut.push_back(node->val); inorderTraverseBT(vOut, node->right); } vector inorderTraversal(TreeNode* root) { vector vRet; inor..

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description Q. 정렬된 배열이 회전 되어서 주어질 때, 이 배열 값 중 최소 값을 구하라. Solution. Binary search 문제 중 단골이다. 풀이법을 반드시 알아야 하겠다. 정렬된 배열을 회전하면, 5가지 경우가 존재한다. // 1, 2, 3, 4, 5 // 5, 1, 2, 3, 4 // 4, 5, 1, 2, 3, // 3, 4, 5, 1, 2 // 2, 3, 4, 5, 1 최소값이 되는 지점을 left, mid, right로 놓고 전개하면 3가지 branch가 나온다. // 1, 2, 3, 4, 5 - left // 5, 1, 2, 3, 4 - mid A // ..

https://leetcode.com/problems/binary-tree-maximum-path-sum/description Q. 한 노드에서 다른 노드까지의 과정을 경로라고 할때, 이 경로의 과정 중, 최대 합을 구하라. 경로에서 모든 노드는 한번씩만 등장 할 수 있다. Solution. 특정 노드 기준, 왼쪽경로 + 오른쪽경로 + 노드값 이 값의 최대값을 구하라는 것이다. 따라서 이 값이 최대값인지 확인하려면, 결국 모든 노드에 대해 이 계산을 해야 할 것이다. 일단 leaf 노드는 자신의 값이 최종 최대값이 될 것이다. 이를 염두하고 모든 노드에 대해 이 연산을 할 수 있다. 또한 윗 노드에서도 현재노드의 값을 이용해서 같은 연산을 해야 한다. 따라서 윗 노드에는 한쪽 최대값과 현재노드 합 중 큰..

https://leetcode.com/problems/search-a-2d-matrix/description Search a 2D Matrix - LeetCode Can you solve this real interview question? Search a 2D Matrix - You are given an m x n integer matrix matrix with the following two properties: * Each row is sorted in non-decreasing order. * The first integer of each row is greater than the last integer leetcode.com Q. 주어진 matrix가 좌에서 우로, 상에서 하로 오름차순 정렬되..