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&×[ch1]!=-1;
int ch2_exist=ch2<len&×[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",×[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;
}
