Python每日一题(13)

一、简述

  今天先不做题，对昨天的二叉树题目分析一下，整体上有些混乱，现在来梳理一下，看看问题在哪，以及应该注意什么。

二、题目再现

  下面的两个题目，我们暂且称为题目1和题目2。

1、昨天每日一题

题目描述

有一个 $n(n\le 10^6)$ 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 $n$），建立一棵二叉树（根节点的编号为 $1$），如果是叶子结点，则输入 0 0。

建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

输入格式

第一行一个整数 $n$，表示结点数。

之后 $n$ 行，第 $i$ 行两个整数 $l$、$r$，分别表示结点 $i$ 的左右子结点编号。若 $l=0$ 则表示无左子结点，$r=0$ 同理。

输出格式

一个整数，表示最大结点深度。

输入输出样例

输入

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

输出

4

2、另一种输入情况的类似题目

  这个题目是写函数，二叉树构建好了，然后这是具体构建描述及代码，详细地就不给全了，看一下题目描述就行。

题目描述

编写函数计算二叉树的深度以及叶子节点数。二叉树采用二叉链表存储结构

//二叉链表存储结构定义
typedef int TElemType;
typedef struct BiTNode{
    TElemType data;
    struct BiTNode  *lchild, *rchild; 
} BiTNode, *BiTree;

//创建二叉树各结点，输入零代表创建空树
//采用递归的思想创建
//递归边界：空树如何创建呢：直接输入0；
//递归关系：非空树的创建问题，可以归结为先创建根节点，输入其数据域值；再创建左子树；最后创建右子树。左右子树递归即可完成创建！

Status CreateBiTree(BiTree &T){
   TElemType e;
   scanf("%d",&e);
   if(e==0)T=NULL;
   else{
     T=(BiTree)malloc(sizeof(BiTNode));
     if(!T)exit(OVERFLOW);
     T->data=e;
     CreateBiTree(T->lchild);
     CreateBiTree(T->rchild);
   }
   return OK;  
}

输入

1 3 0 0 5 7 0 0 0

输出

3 2

  输出第一个3是深度，第二个2是叶子数。

三、分析

  认真读一下题目，可以看到，本质上都是一样的，求深度。昨天也说过了，求深度的话需要左右子树递归，并返回其最大值+1，不论这两个题目怎么样，求深度的这一点是不变的。那么问题出现在了哪里呢？二叉树的创建上。
  二叉树的创建肯定不是死板的，而根据其输入情况的不同，二叉树的创建肯定也不一样。题目2中数据的输入，结合其内部二叉树创建的描述，可以知道是先序输入的。而题目1的输入肯定不是先序输入，跟层序输入类似，但也不是层序输入。根据我的分析，其样子应该是想下面这样的。

  如果层序输入的话，遍历应该是：1 2 7 3 6 0 0 4 5 0 0 0 0 0 0，因此如果层序输入的话，也应该是这个。不过我们根据其输入情况来看，它是优先生成左子树，然后再生成右子树的，这样的话，满足我们递归求深度的条件（左右子树分别递归），不过问题就在于二叉树的创建。不能再用题目二那样的创建方式了，肯定不符合的。我大体看了一下其他的创建方式，由于左侧都是左子树，右侧都是右子树，那么就用两个数组分别存储左右结点编号，然后再dfs分别递归左右子树。所以此时的创建需要两个数组，不过这个数组是“有序”的，而如果先序输入的话，只能像昨天那种创建方式，因为这种是类似于“无序”的，需要将左右子树判断分开。
  另外既然有先序输入，那么也会有中序、后续输入的情况，我查了查，大部分二叉树创建都是先序输入的，其他类型的似乎没有。然后问了问gpt，它给出了方法，但是有一定限制，所以建议先不考虑这两种情况。后续有这种奇怪输入方式的题目的话，再另作分析。

四、答案

  下面这个c语言是洛谷里小伙伴给的，可以参考一下。

#include <iostream>
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
using namespace std;

const int MAXN = 1e6 + 10;

struct node {
    int left, right;
};
node tree[MAXN];//存储结构定义

int n, ans;

void dfs(int id, int deep) {
    if (id == 0) return ;//到达叶子节点时返回
    ans = max(ans, deep);//更新答案
    dfs(tree[id].left, deep+1);//向左遍历
    dfs(tree[id].right, deep+1);//向右遍历
}

int main() {
    cin >> n;
    _for (i, 1, n) cin >> tree[i].left >> tree[i].right;//读入+建树
    dfs(1, 1);//从1号节点出发，当前深度为1
    cout << ans << endl;//输出答案
    return 0;//完结撒花！
}

  下面这个是昨天ac的python代码，deepseek写的，整体思路跟上面类似。

n = int(input())
left = [0] * (n + 1)
right = [0] * (n + 1)

for i in range(1, n + 1):
    l, r = map(int, input().split())
    left[i] = l
    right[i] = r

def max_depth(node):
    if node == 0:
        return 0
    return max(max_depth(left[node]), max_depth(right[node])) + 1

print(max_depth(1))

五、总结

  首先要明确，人是灵活的。我们所学的，跟题目可能有些不同，本质不清楚，换种方式问，可能还会错，所以掌握本质才是根本。另外，有了思路之后还需要自己再写一写，要不然不熟练，之后肯定还会再出问题的。