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

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