二叉树的层序遍历/后序遍历（leetcode104二叉树的最大深度、111二叉树的最小深度）（华为OD悄悄话、数组二叉树）

2024-07-05 19:54:50

104二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
在这里插入图片描述
本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
我先用后序遍历（左右中）来计算树的高度。

1、确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
代码如下：

int getdepth(TreeNode* node)
2、确定终止条件：如果为空节点的话，就返回0，表示高度为0。
代码如下：
```c
if (node == NULL) return 0;
3、确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
代码如下：
`int leftdepth = getdepth(node->left);       // 左
int rightdepth = getdepth(node->right);     // 右
int depth = 1 + max(leftdepth, rightdepth); // 中
return depth;``

``int maxDepth(struct TreeNode* root) {
    if(root==NULL) return 0;
    int left=maxDepth(root->left);
    int right=maxDepth(root->right);
    return 1+fmax(left,right);
}

111、二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
在这里插入图片描述

1 、递归法（后序遍历）

I、确定递归函数的参数和返回值
参数为要传入的二叉树根节点，返回的是int类型的深度。
代码如下：

int getDepth(TreeNode* node)
II、确定终止条件
终止条件也是遇到空节点返回0，表示当前节点的高度为0。
代码如下：

```c
if (node == NULL) return 0;

III、确定单层递归的逻辑

int leftDepth = getDepth(node->left);           // 左
int rightDepth = getDepth(node->right);         // 右
                                                // 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) { 
    return 1 + rightDepth;
}   
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) { 
    return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;

int minDepth(struct TreeNode* root) {
    if(root==NULL) return 0;
    int left= minDepth(root->left);
     int right= minDepth(root->right);
    if(root->left==NULL&&root->right!=NULL)
        return 1+right;
    if(root->left!=NULL&&root->right==NULL)
        return 1+left;
    return 1+fmin(left,right);   
}

2、迭代法（层序遍历）

int minDepth(struct TreeNode* root) {
    struct TreeNode* q[10000];
    if(root==NULL) return 0;
    int depth=0;
    int l=0,r=0;
    q[r++]=root;//将根节点入栈
    while(l<r){
        depth++;
        int len=r-l;
        for(int i=0;i<len;i++){
            root=q[l++];//队头元素为根节点
            if(root->left==NULL&&root->right==NULL)
            return depth;
            if(root->left!=NULL)
            q[r++]=root->left;
            if(root->right!=NULL)
            q[r++]=root->right;
        }
    }
    return depth;
}

华为OD机试C卷（100分）-悄悄话

题目描述

给定一个二叉树，每个节点上站一个人，节点数字表示父节点到该节点传递悄悄话需要花费的时间。
初始时，根节点所在位置的人有一个悄悄话想要传递给其他人，求二叉树所有节点上的人都接收到悄悄话花费的时间。

输入描述

给定二叉树

0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

注：-1表示空节点
在这里插入图片描述

输出描述

返回所有节点都接收到悄悄话花费的时间
38

用例

输入 0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
输出 38
说明 无

题目解析

题目给的输入信息对照图示来看，应该就是二叉树的层序遍历序列，如下图所示：
在这里插入图片描述
层序遍历序列中，父子节点存在如下关系：
如果父节点在序列中的索引是k，则其两个子节点在序列中的索引分别为 2k+1, 2k+2
因此，我们就无需建树操作了。
而悄悄话的传递，其实父节点将自身得到消息的时延累加到其各个子节点上，最终叶子节点中最大的时延值就是：二叉树所有节点上的人都接收到悄悄话花费的时间
在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>
int getResult(int *times,int len){
     int ans=0;
     int queue[100];
     int front=0,rear=0;
     queue[rear++]=0;
     while(front<rear){
          int fa=queue[front++];
          int ch1=2*fa+1;
          int ch2=2*fa+2;
          int ch1_exist=ch1<len&&times[ch1]!=-1;
           int ch2_exist=ch2<len&&times[ch2]!=-1;
           if(ch1_exist){
               times[ch1]+=times[fa];
               queue[rear++]=ch1;
           }
           if(ch2_exist){
               times[ch2]+=times[fa];
               queue[rear++]=ch2;
           }
           if(!ch1_exist&&!ch2_exist){
               if(times[fa]>ans)
                    ans=times[fa];
           }
     }
     return ans;
}
int main()
{
     int times[1000];
     int len=0;
     while(scanf("%d",&times[len++])){
          if(getchar()!=' ')break;
     }
    printf("%d\n",getResult(times,len));
    return 0;
}

华为OD机试(C卷,200分)- 数组二叉树

题目描述

二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2N和2N+1，并且我们用值-1代表一个节点为空。
给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。

输入描述

输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。
注意第一个元素即为根节点的值，即数组的第N个元素对应下标N，下标0在树的表示中没有使用，所以我们省略了。
输入的树最多为7层。

输出描述

输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个。

用例

输入 3 5 7 -1 -1 2 4
输出 3 7 2
说明 最小叶子节点的路径为3 7 2。
输入 5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6
输出 5 8 7 6
说明 最小叶子节点的路径为5 8 7 6，注意数组仅存储至最后一个非空节点，故不包含节点“7”右子节点的-1。

题目解析

本题有两种思路，一种是从树顶节点向下找，直到找到最小值节点。
这种方式是典型的深度优先搜索。
在这里插入图片描述
还有一种思路是先找到最小值节点，然后从最小值节点向上找父节点，由于向上找只有一个父节点，因此只有一种路径。
因此，我们应该选择这种方式。
在这里插入图片描述
采用这种方式，首先需要找到最小值节点在数组中的索引位置idx，然后根据题目定义的规则
对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2N和2N+1
当然上面这个规则是针对根节点索引从1开始的，如果根节点索引从0开始算法，则上面规则应变为
对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2N+1和2N+2
每找到一个父节点，就将其当成新的子节点，继续向上找父节点，直到子节点本身就是树顶节点为止。
另外，如何找到最小值叶子节点呢？
我们可以反向遍历输入的节点数组，如果遍历的节点符合下面条件，那么他就是一个叶子节点：
自身节点值不为-1
自身没有子节点（即既没有左子节点，也没有右子节点）

#include <stdio.h>
#include <limits.h>
#define MAXSIZE INT_MAX
char* getResult(int arr[], int size) {
    // 最小叶子节点的值
    int minV = MAXSIZE;
    // 最小节点在数组中的索引位置
    int minIdx = -1;
    int n = size - 1;

    for (int i = n; i > 0; i--) {
        if (arr[i] != -1) {
            if (i * 2 + 1 <= n && arr[i * 2 + 1] != -1) {
                continue;
            }
            if (i * 2 + 2 <= n && arr[i * 2 + 2] != -1) {
                continue;
            }

            if (minV > arr[i]) {
                minV = arr[i];
                minIdx = i;
            }
        }
    }

    // path 用于缓存最小叶子节点到根的路径
    char* path = (char*)malloc(100 * sizeof(char));
    int pathIndex = 0;
    char temp[10];
    sprintf(temp, "%d", minV);
    for (int i = 0; temp[i] != '\0'; i++) {
        path[pathIndex++] = temp[i];
        path[pathIndex++] = ' ';
    }

    // 从最小值节点开始向上找父节点，直到树顶
    while (minIdx != 0) {
        int f = (minIdx - 1) / 2;
        sprintf(temp, "%d", arr[f]);
        for (int i = 0; temp[i] != '\0'; i++) {
            path[pathIndex++] = temp[i];
        }
        path[pathIndex++] = ' ';
        minIdx = f;
    }


    path[pathIndex] = '\0';

    return path;
}
void reverseString(char* str) {
    int length = strlen(str)-1;
    for (int i = 0; i < length / 2; i++) {
        char temp = str[i];
        str[i] = str[length - i - 1];
        str[length - i - 1] = temp;
    }
}
int main() {
    // 输入数组
    int arr[1000];
    int n=0;
    while(scanf("%d",&arr[n++])){
     if(getchar()!=' ')break;
    }

    // 调用算法函数
    char* result =getResult(arr, n);
     reverseString(result);

    // 输出结果
    printf("%s\n", result);

    // 释放内存
    free(result);

    return 0;
}
上一篇：20240701给NanoPi R6C开发板编译友善之臂的Android12系统


下一篇：基于Linux的云端垃圾分类助手-功能实现