tree (7) 썸네일형 리스트형 [코딩인터뷰 완전정복] 4.12 합의 경로 Q : 각 노드의 값이 정수(음수 및 양수)인 이진 트리가 있다. 이때 정수의 합이 특정 값이 되도록 하는 경로의 개수를 세려고 한다. 경로가 꼭 루트에서 시작해서 말단 노드에서 끝날 필요는 없지만 반드시 아래로 내려가야 한다. 즉, 부모 노드에서 자식 노드로만 움직일 수 있다. 알고리즘을 어떻게 설계할 것인가? 1. Brute Force 모든 노드에 대해 해당 노드가 시작점이 되는 경로가 존재하는지 확인 한다. 한 노드를 시작점으로 잡는다. 시작점에서 깊이 우선 탐색을 이용해 탐색하며, 시작점에서 각 노드까지의 합을 기록한다. 합이 특정 값이 되는 노드의 갯수를 샌다. 모든 노드에 대해 반복한 후 그 수 모두 더해 반환한다. 2. 트리를 한번만 순회하는 방법 각 노드가 자신의 부모들로 부터 자신까지 더.. [코딩인터뷰 완전정복] 4.11 임의의 노드 Q : 이진 트리 클래스를 바닥부터 구현하려고 한다. 노드의 삽입, 검색, 삭제 뿐만 아니라 임의의 노드를 반환하는 getRandomNode() 메서드도 구현한다. 모든 노드를 같은 확률로 선택해주는 getRandomNode() 메서드를 설계하고 구현하라. 또한 나머지 메서드는 어떻게 구현할지 설명하라. 구현 요소 : 노드 노드의 삽입 노드의 검색 노드의 삭제 getRandomNode() -> 임의의 노드를 선택하여 반환해준다. 모든 노드가 같은 확률로 선택된다. Node.h 보기 // node.h template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this-.. [코딩인터뷰 완전정복] 4.8 첫 번째 공통 조상 Q : 이진 트리에서 노드 두개가 주어졌을 때 이 두 노드의 첫번째 공통 조상을 찾는 알고리즘을 설계하고 그 코드를 작성하라. 자료구조내에 추가로 노드를 저장해 두면 안 된다. 반드시 이진 탐색 트리일 필요는 없다. 1. brute force (무식한 방법) 한 노드의 조상들과 다른 노드의 조상들을 모두 비교해보면, 두 노드가 공통된 조상을 가지고 있는지 알아낼 수 있을 것이다. 우리는 두 노드의 첫번째 공통 조상을 찾아야 하기 때문에, 자식에서 부모순서로 탐색한다. 한 노드의 조상들을 다른 노드의 모든 조상 노드들과 비교하기 때문에 시간복잡도는 O(MN) 이다. 이때, M과 N은 각 노드의 조상 노드의 갯수이다. 임의의 노드 2개를 각각 A, B라고 하겠다. A의 부모노드 A'과 B의 모든 부모노드들을.. [코딩인터뷰 완전정복] 4.6 후속자 Q : 이진 탐색 트리에서 주어진 노드의 '다음' 노드(중위 후속자(in-order successor))를 찾는 알고리즘을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자. ...더보기 // Node.h template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } void addLeft(TreeNode* left) { this->left = left; left->parent = this; } void addRight(TreeNode* right) { this->right = right; right->paren.. [코딩인터뷰 완전정복] 4.5 BST 검증 Q : 주어진 이진 트리가 이진 탐색 트리인지 확인하는 함수를 작성하라. ...더보기 //Node.h template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } }; #include #include "Node.h" bool isBST(TreeNode* top, int low, int high) { if (top == NULL) return true; if (low != NULL && top->data data >= high) return false; bool left = isBST(top->left, low, top->data);.. [코딩인터뷰 완전정복] 4.4 균형 확인 Q : 이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다. ...더보기 // Node.h template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } }; #include #include "Node.h" int checkBalanced(TreeNode* top) { int left = top->left == NULL ? 1 : checkBalanced(top->left) + 1; int ri.. [코딩인터뷰 완전정복] 4.3 깊이의 리스트 Q : 이진 트리가 주어졌을 때 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘을 설계하라. 즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어야 한다. ...더보기 template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } }; template class ListNode { T data; ListNode* previous; ListNode* next; ListNode(T data) { this->data = data; } }; #include #include #include #include "Node.h" using.. 이전 1 다음
