求结点最大深度，洛谷洛谷P4913

Question

洛谷P4913

第一个样例是对的就是一个都过不了

#include "iostream"
using std::cin;
using std::cout;
using std::endl;
int n,a,b,temp=1;
int max;
struct Tree{
    int data;
    struct Tree* lchild;
    struct Tree* rchild;
};

void dfs(int x, Tree* T) {
    if (T == NULL)
        return;
    if (T->data == x)
    {
        if (a != 0) {
            Tree* q = new Tree;
            q->data = a;
            T->lchild = q;
            q->lchild = NULL;
            q->rchild = NULL;
        }
        else T->lchild = NULL;
        if (b != 0) {
            Tree* p = new Tree;
            p->data = b;
            T->rchild = p;
            p->lchild = NULL;
            p->rchild = NULL;
        }
        else T->rchild = NULL;
        return;
    }
    dfs(x, T->lchild);
    dfs(x, T->rchild);
}

void dfs2(Tree* T, int temp) {
    if (T == NULL) {
        if (temp - 1 > max)
        {
            max = temp - 1;
        }
        return;
    }
    dfs2(T->lchild, temp + 1);
    dfs2(T->rchild, temp + 1);
    
}
int main() {
    cin >> n;
    Tree* root = new Tree;
    root->data = 1;
    cin >> a >> b;
    if (a != 0) {
        Tree* q = new Tree;
        q->data = a;
        root->lchild = q;
        q->lchild = NULL;
        q->rchild = NULL;
    }
    else root->lchild = NULL;
    if (b != 0) {
        Tree* p = new Tree;
        p->data = b;
        root->rchild = p;
        p->lchild = NULL;
        p->rchild = NULL;
    }
    else root->rchild = NULL;
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        dfs(i + 1, root);
    }
    dfs2(root,temp);
    cout << max;
}

Answer 1

引自免费微信小程序：皆我百晓生

问题：求结点最大深度

解决方案如下：

1. 确定结点的树类型：树的结点类型是struct Tree，包含数据data，左子树lchild和右子树rchild。
2. 实现深度优先搜索函数dfs：
   • 函数参数为目标值x和当前的树T。
   • 如果当前树为空，返回。
   • 如果当前树的数据等于目标值x，则根据变量a和b的值构建左子树和右子树。如果a不为0，则创建q作为左子树，并设置其数据为a；否则，将左子树设置为空。如果b不为0，则创建p作为右子树，并设置其数据为b；否则，将右子树设置为空。然后返回。
   • 否则，递归地对当前树的左子树调用dfs函数，并将目标值x传递下去。然后，递归地对当前树的右子树调用dfs函数，并将目标值x传递下去。
3. 实现深度优先搜索函数dfs2：
   • 函数参数为当前的树T和临时深度temp。
   • 如果当前树为空，判断临时深度temp-1是否大于最大深度max，如果是，则更新最大深度。
   • 否则，递归地对当前树的左子树调用dfs2函数，并将临时深度temp+1传递下去。然后，递归地对当前树的右子树调用dfs2函数，并将临时深度temp+1传递下去。
4. 在主函数main中：
   • 读取结点个数n。
   • 创建根结点root，数据设为1。
   • 读取a和b的值，如果a不为0，则创建q作为根结点的左子树，数据设为a；否则，将左子树设置为空。如果b不为0，则创建p作为根结点的右子树，数据设为b；否则，将右子树设置为空。
   • 使用循环从1到n-1，依次读取a和b的值，并调用dfs函数。
   • 调用dfs2函数，将根结点传递给它，并临时深度设为起始值temp。
   • 输出最大深度max。

完整的代码如下所示：

#include "iostream"
using std::cin;
using std::cout;
using std::endl;
int n, a, b, temp = 1;
int max;
struct Tree {
    int data;
    struct Tree* lchild;
    struct Tree* rchild;
};

void dfs(int x, Tree* T) {
    if (T == NULL)
        return;
    if (T->data == x)
    {
        if (a != 0) {
            Tree* q = new Tree;
            q->data = a;
            T->lchild = q;
            q->lchild = NULL;
            q->rchild = NULL;
        }
        else T->lchild = NULL;
        if (b != 0) {
            Tree* p = new Tree;
            p->data = b;
            T->rchild = p;
            p->lchild = NULL;
            p->rchild = NULL;
        }
        else T->rchild = NULL;
        return;
    }
    dfs(x, T->lchild);
    dfs(x, T->rchild);
}

void dfs2(Tree* T, int temp) {
    if (T == NULL) {
        if (temp - 1 > max)
        {
            max = temp - 1;
        }
        return;
    }
    dfs2(T->lchild, temp + 1);
    dfs2(T->rchild, temp + 1);
}

int main() {
    cin >> n;
    Tree* root = new Tree;
    root->data = 1;
    cin >> a >> b;
    if (a != 0) {
        Tree* q = new Tree;
        q->data = a;
        root->lchild = q;
        q->lchild = NULL;
        q->rchild = NULL;
    }
    else root->lchild = NULL;
    if (b != 0) {
        Tree* p = new Tree;
        p->data = b;
        root->rchild = p;
        p->lchild = NULL;
        p->rchild = NULL;
    }
    else root->rchild = NULL;
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        dfs(i + 1, root);
    }
    dfs2(root, temp);
    cout << max;
}

请注意，在主函数中，为了简化代码，我没有重新定义变量max和temp的初始值，所以在声明它们之前，最好先将它们初始化为0。

希望能对你有所帮助！如有任何疑问，可以随时继续提问。