Đếm số cây con đơn lẻ

Question

Tôi đã viết một số mã để giải quyết câu hỏi phỏng vấn sau đây. Xin vui lòng cho biết làm thế nào nó có thể được cải thiện. Cảm ơn trước.

Cây đơn nguyên (viết tắt của "giá trị phổ quát") là cây mà tất cả các nút bên dưới nó đều có cùng giá trị. Cho gốc của cây nhị phân, hãy đếm số lượng cây con đơn lẻ. Ví dụ, cây sau đây có 5 cây con đơn lẻ:

    0
   / \
  1   0
     / \
    1   0
   / \
  1   1

Thực hiện:

#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);

}

Answer 1

Định dạng mã

1. Đặt loại thẻ xuống hai dòng thay vì trên cùng một dòng như dấu ngoặc nhọn đóng là điều gây tò mò.

Quản lý cây xanh

1. Tôi tự hỏi tại sao bạn không sử dụng createNode()trong insertRight()và insertLeft().

2. Nếu bạn chuyển sang xây dựng cây từ lá xuống gốc thay vì ngược lại, bạn chỉ cần createNode()một giá trị chấp nhận duy nhất và hai (có thể NULL) con cháu.

3. Giả sử rằng việc cung cấp tài nguyên-thủy sản luôn thành công là khá dũng cảm.

4. Hãy xem xét thêm một cách để giải phóng một cái cây, để có hiệu quả tốt nhất bằng cách sử dụng không gian cố định, mặc dù việc sử dụng nó ngay trước khi phá bỏ toàn bộ quá trình là lãng phí một cách vô lý.

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);
    }
}

Phần chính

1. Nếu bạn không cần sửa đổi điều gì đó, thì không cần quyền. Sử dụng const.

2. isTreeUniv()chỉ là bị hỏng . Nó chỉ kiểm tra con cháu trực tiếp, trong khi nó sẽ đệ quy lại chúng.

3. Do đó, countUnivSubT()cũng sai. Tuy nhiên, việc sửa chữa isTreeUniv()sẽ dẫn đến \$O(n^2)\$thuật toán, khi nó phải được \$O(n)\$. Ý tưởng là có được tất cả thông tin bạn cần cùng một lúc.

4. Tránh hình cầu. Việc sử dụng uTreeCountlàm cho mã không thể nhập lại và phá vỡ vị trí lập luận.

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);
}

Answer 2

Một lá cờ đỏ là uTreeCount. Đây không phải là một toàn cục và trên thực tế, thật dễ dàng để diễn đạt lại của bạn countUnivSubTđể trở thành người đăng ký lại hoàn toàn: đặt nó trả về một số nguyên và thực hiện phép cộng trong phần nội dung, giống như

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;
}

Điều đó nói rằng, bạn có một kiểm tra rỗng bên trong, vì vậy điều này thực sự có thể giảm xuống

unsigned countUnivSubT(stTree *Node)
{
    if (!Node) return 0;
 
    return isTreeUniv(Node)
        + countUnivSubT(Node->left)
        + countUnivSubT(Node->right);
}

Answer 3

const

Hãy xem xét constcác hàm không làm thay đổi cây:

//  bool isTreeUniv(stTree *node)
bool isTreeUniv(const stTree *node)

//void countUnivSubT(stTree *Node)
void countUnivSubT(const stTree *Node)

Điều này cải thiện sự rõ ràng của mã làm gì và cho phép tối ưu hóa được chọn.

Cơ hội lặp lại so với đệ quy

Thay vì một cuộc gọi toàn cục và hai cuộc gọi đệ quy, có thể lặp lại ở một bên và đệ quy ở bên kia:

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;
}

Answer 4

Thuật toán không hiệu quả.

Đối với mỗi nút, chúng tôi kiểm tra tất cả các nút trong cây con của nó để xác định xem chúng có bằng nhau hay không. Chúng ta nên xem mỗi nút chỉ một lần và trích xuất bao nhiêu tùy ý trong lần truy cập duy nhất đó. Vì vậy, khi chúng ta bắt đầu, hãy báo cáo lại xem nút hiện tại có phải là cây đơn nhất hay không, cũng như số lượng cây đơn nhất ở hoặc dưới nó. Chúng ta không cần đến thăm bọn trẻ một lần nữa, chỉ cần sử dụng thông tin truy xuất được. Như thế này:

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);
}

Và sử dụng nó trong main():

printf("There are %zu universal subtrees\n",
       countUnivSubT(rootNode));

(Tôi cũng đã sửa lỗi chính tả ở đó).