유니 벌 하위 트리 계산
다음 인터뷰 질문을 해결하기 위해 코드를 작성했습니다. 개선 할 수있는 방법을 알려주십시오. 미리 감사드립니다.
유니 벌 트리 ( "유니버설 값"을 의미)는 그 아래의 모든 노드가 동일한 값을 갖는 트리입니다. 이진 트리의 루트가 주어지면 유니 벌 하위 트리의 수를 세십시오. 예를 들어, 다음 트리에는 5 개의 유니 벌 하위 트리가 있습니다.
0
/ \
1 0
/ \
1 0
/ \
1 1
이행:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct stTree
{
struct stTree * left;
struct stTree * right;
int value;
}
stTree;
stTree* createNode(int value)
{
stTree *node = malloc(sizeof *node);
node->left = NULL;
node->right = NULL;
node->value = value;
return node;
}
bool isTreeUniv(stTree *node)
{
bool flag = true;
if (!node)
return false;
if (node->right && node->right->value != node->value)
{
flag = false;
}
if (node->left && node->left->value != node->value)
{
flag = false;
}
return flag;
}
stTree* insertRight(stTree *currNode, int value)
{
stTree *node = malloc(sizeof *node);
currNode->right = node;
node->left = NULL;
node->right = NULL;
node->value = value;
return node;
}
stTree* insertLeft(stTree *currNode, int value)
{
stTree *node = malloc(sizeof *node);
currNode->left = node;
node->left = NULL;
node->right = NULL;
node->value = value;
return node;
}
unsigned int uTreeCount = 0;
void countUnivSubT(stTree *Node)
{
if (isTreeUniv(Node))
uTreeCount++;
if (Node->left)
countUnivSubT(Node->left);
if (Node->right)
countUnivSubT(Node->right);
}
int main(void)
{
//build a tree
stTree *rootNode = createNode(0);
insertLeft(rootNode, 1);
insertRight(rootNode, 0);
insertLeft(rootNode->right, 1);
insertRight(rootNode->right, 0);
insertLeft(rootNode->right->left, 1);
insertRight(rootNode->right->left, 1);
countUnivSubT(rootNode);
printf("total universal subree: %u\n", uTreeCount);
}
답변
코드 서식
- 닫는 중괄호와 같은 줄이 아닌 태그 유형의 두 줄을 아래로 놓는 것이 궁금합니다.
나무 관리
및
createNode()에서 사용하지 않는 이유가 궁금합니다 .insertRight()insertLeft()반대로 잎에서 뿌리까지 나무를 만드는 것으로 변경하는 경우
createNode()값을 받아들이는 단일 항목 과 두 개의NULL하위 항목 만 필요합니다 .자원 수집이 항상 성공한다고 가정하는 것은 매우 용감합니다.
전체 프로세스를 분해하기 직전에 사용하는 것은 비양심적으로 낭비이지만 일정한 공간을 사용하여 최상의 효과를 내기 위해 나무를 해제하는 방법을 추가하는 것을 고려하십시오.
stTree* createNode(int value, stTree* left, stTree* right) {
stTree* r = malloc(sizeof *r);
if (!r) abort();
r->value = value;
r->left = left;
r->right = right;
return r;
}
static stTree* findBottomLeft(stTree* node) {
while (node->left)
node = node->left;
return node;
}
void freeTree(stTree* node) {
if (!node) return;
stTree* bottomLeft = findBottomLeft(node);
while (node) {
if (node->right) {
bottomLeft->left = node->right;
bottomLeft = findBottomLeft(bottomLeft);
}
stTree* old = node;
node = node->left;
free(old);
}
}
주요 부분
무언가를 수정할 필요가 없다면 권리를 요구하지 마십시오. 사용
const.isTreeUniv()그냥 깨졌습니다 . 직계 하위 항목 만 확인하고 재귀해야합니다.결과적으로
countUnivSubT()잘못되었습니다. 그래도 수정isTreeUniv()하면 \$O(n^2)\$알고리즘, \$O(n)\$. 아이디어는 필요한 모든 정보를 한 번에 얻는 것입니다.글로벌을 피하십시오. 를 사용
uTreeCount하면 코드가 재진입되지 않고 추론의 지역성이 깨집니다.
static bool countUnivSubTimpl(const stTree* node, const stTree* parent, size_t* count) {
if (!node) return true;
bool r = countUnivSubTimpl(node->left, node, count)
& countUnivSubTimpl(node->right, node, count);
*count += r;
return r & node->value == parent->value;
}
size_t countUnivSubT(const stTree* node) {
size_t r = 0;
countUnivSubTimpl(node, node, &r);
return r;
}
int main() {
stTree* root =
createNode(0,
createNode(1, NULL, NULL),
createNode(0,
createNode(1,
createNode(1, NULL, NULL),
createNode(1, NULL, NULL),
),
createNode(0, NULL, NULL)));
size_t uTreeCount = countUnivSubT(root);
printf("total universal subree: %u\n", uTreeCount);
}
하나의 붉은 깃발은 uTreeCount입니다. 이것은 전역 적이 어서는 안되며 실제로 countUnivSubT완전히 재진입 하도록 다시 표현하는 것은 쉽습니다 . 정수를 반환하고 본문 내에서 덧셈을 수행합니다.
unsigned countUnivSubT(stTree *Node)
{
unsigned int uTreeCount = isTreeUniv(Node);
if (Node->left)
uTreeCount += countUnivSubT(Node->left);
if (Node->right)
uTreeCout += countUnivSubT(Node->right);
return uTreeCount;
}
즉, 내부 null 검사가 있으므로 실제로 다음과 같이 줄일 수 있습니다.
unsigned countUnivSubT(stTree *Node)
{
if (!Node) return 0;
return isTreeUniv(Node)
+ countUnivSubT(Node->left)
+ countUnivSubT(Node->right);
}
const
const트리를 변경하지 않는 함수를 고려하십시오 .
// bool isTreeUniv(stTree *node)
bool isTreeUniv(const stTree *node)
//void countUnivSubT(stTree *Node)
void countUnivSubT(const stTree *Node)
이렇게하면 코드가 수행하는 작업의 명확성이 향상되고 선택 최적화가 가능합니다.
루프 기회 vs 재귀
전역 및 두 개의 재귀 호출 대신 한 쪽에서 반복하고 다른 쪽에서 반복 할 수 있습니다.
unsigned countUnivSubT(const stTree *Node) {
unsigned count = 0;
while (Node) {
count += isTreeUniv(Node);
if (Node->left) {
count += countUnivSubT(Node->left);
}
Node = Node->right;
}
return count;
}
알고리즘이 비효율적입니다.
각 노드에 대해 하위 트리의 모든 노드를 검사하여 모두 동일한 지 확인합니다. 각 노드를 한 번만 방문하고 해당 단일 방문에서 필요한만큼 추출해야합니다. 따라서 현재 노드가 유니 벌 트리인지 여부와 그 이하의 유니 벌 트리 수를보고합니다. 우리는 아이들을 다시 방문 할 필요가 없으며 검색된 정보를 사용하기 만하면됩니다. 이렇게 :
static size_t countUnivSubT_impl(const stTree *node, bool *isUnival, int *value)
{
if (!node) {
return 0;
}
*value = node->value;
/* initial values chosen to work if one/both children are null */
int lval = node->value, rval = node->value;
bool lunival = true, runival = true;
size_t count_left = countUnivSubT_impl(node->left, &lunival, &lval);
size_t count_right = countUnivSubT_impl(node->right, &runival, &rval);
return count_left + count_right
+ (*isUnival = /* N.B. assignment */
lunival && lval == node->value &&
runival && rval == node->value);
}
size_t countUnivSubT(const stTree *node)
{
bool isUnival;
int value;
return countUnivSubT_impl(node, &isUnival, &value);
}
그리고 그것을 사용하십시오 main():
printf("There are %zu universal subtrees\n",
countUnivSubT(rootNode));
(저도 거기에서 철자를 수정했습니다).