Apes Together Strong.

https://leetcode.com/problems/surrounded-regions/description  Q. 외부 경계에 접하지 않고, x 에 둘러싸인 영역을 "surrounded"라고 표현할 때, 이 surrounded된 영역의 O를 모두 X로 변환하라.   Solution.  우선 O로 연결된 영역을 방문관리를 하면서 찾는다.  다만, 이때 외부에 걸친 영역이 존재한다면, surrounded되지 않았고, surrounded되었다면 이 영역의 O를 X로 변경한다.   코드  더보기void BFS(vector>& board, int ix, int iy, vector& vVisit){ int H = board.size(); int W = board[0].size(); queue qB..

Q. 주어진 BST 에서 두 노드간 차이의 절대값의 최소값을 찾아라.  Solution.  BST 자체가 우선 정렬된 값이라는 것을 생각할 필요가 있다.  그렇다면 이 정렬된 값을 어떻게 얻느냐.  In Order Traverse를 하면 정렬된 값을 순서대로 얻을 수가 있다.   코드를 만든다. 더보기 void InOrder(TreeNode* node, vector& vBuff){ if(node == nullptr) return; InOrder(node->left, vBuff); vBuff.push_back(node->val); InOrder(node->right, vBuff);}int getMinimumDifference(TreeNode* root) { vecto..

주어진 Binary Tree에 대해 각 level당 value값을 zig zag로 수집하고, 결과를 출력하라.  Solution. level의 노드를 문제의 의도대로 교차 접근한다.  Easy 난이도에 더 가까운 문제.   코드 더보기vector> zigzagLevelOrder(TreeNode* root) { vector> vRet; if(root == nullptr) return vRet; queue qBuff; qBuff.push(root); bool dirLeftToRight = true; while(qBuff.size() > 0) { int cnt = qBuff.size(); vector vLevelNodes; ..

Q. 주어진 Binary Tree의 level당 평균값을 구하고, 그 값을 출력하라.   Solution BFS의 기본 문제.  각 level당 queue의 count를 이용해 레벨 노드의 정보를 얻어 결과 계산.   코드  더보기 vector averageOfLevels(TreeNode* root) { vector vOut; if(root == nullptr) return vOut; queue qBuff; qBuff.push(root); while(qBuff.size() > 0) { int cnt = qBuff.size(); double val = 0; for(int q = 0; q val); ..

Q. 주어진 binary tree를 in order traverse 한다고 할 때 아래 class를 디자인 하라.   이때 next()와 HasNext()에 대해 O(1) TC와 O(h)의 mem space사용을 하도록 하라.   Solution.  위 제한이 없다면, 객체 초기화 시점에 모든 데이터를 in order traverse하고 collect하고자 하는 데이터를 list등의 컨테이너에 넣으면 될 것이다.  하지만 제한으로 인해 다른 구조가 필요하다는 것을 알 필요가 있다.   우선 in order traverse를 하면, 왼쪽 child 이후 해당 노드를 방문하고 우측 child를 순서대로 방문하게 된다.  따라서 전체 순회 시 stack이 필요하다.  또한 높이만큼의 메모리만 사용하라고 했으므..

https://leetcode.com/problems/sum-root-to-leaf-numbers/description   여러 방법이 있을 수 있지만, 직관적인 방법으로 풀어본다. Codes더보기void dfs(TreeNode* node, vector& vBuff, long& sum){ if(node == nullptr) return; vBuff.push_back(node->val); if(node->left==nullptr && node->right==nullptr) { long val = 0; long digit = 1; for(int q = vBuff.size()-1; q >= 0; --q) { ..

https://leetcode.com/problems/path-sum/description  Q. root 에서 leaf까지 가는 경로동안 그 합이 targetSum이 되는 것이 있으면 true를 반환하라.  Solution.  - 단순 경로 탐색 문제.  - 경로를 가는 동안 노드 값을 누적하고, leaf node인 순간 targetSum을 확인한다.  코드 더보기bool hasPathSumToLeaf(TreeNode* node, int targetSum, int sum){ if(node == NULL) return false; sum += node->val; if(node->left==NULL && node->right==NULL) { if(sum == ..

Q. 주어진 트리에서 next 포인터를 위 예시와 같이 지정하도록 하라.   Solution.  BFS 를 알고 있다면 간단한 문제.  depth 별로 node를 추린 후에 뒤에서 부터 next 포인터를 정리한다.  코드 더보기public Node Connect(Node root) { if(root == null) return root; Queue qBuff = new Queue(); qBuff.Enqueue(root); while(qBuff.Count > 0) { int cnt = qBuff.Count; List listNodes = new List(); for(int q = 0; q    결과

Q. inorder 와 postorder 순회 정보가 주어질 때 tree를 구성하라.   Solution.  105번(https://artofcom77.tistory.com/258) 의 응용판 문제.  여기서는 post order 정보를 사용하였으므로, 값을 뒤에서 부터 취하는 것이 중요.  또한 뒤에서 부터 취하므로, tree를 left -> right 가 아닌 그 역순(Right->Left)으로 더해 나가기 시작하는 것에 유의 한다.   코드 더보기  TreeNode BT(Dictionary dictBuffer, int[] postorder, ref int idx, int left, int right){ if(left > right) return null; if(idx=dictBuff..

https://leetcode.com/problems/invert-binary-tree/description Q. Tree를 좌우 반전 하라.  Solution.  Tree의 leaf의 모든 정보를 depth 별로 저장하고, 그 반대로 parnet와 link 하면 될 것 같다.   Code 더보기 public TreeNode InvertTree(TreeNode root) { if(root == null) return root; Queue qBuff = new Queue(); qBuff.Enqueue(root); List> cache = new List>(); int depth = 1; while(qBuff.Count > 0) { int cnt = q..