站长忽略的几个观点,电脑优化软件哪个好用,wordpress菜单显示选项,域名注册商是什么意思题目链接/文章讲解/视频讲解#xff1a; 代码随想录 1.117.填充每个节点的下一个右侧节点指针II
1.1分析及思路
和116.填充每个节点的下一个右侧节点指针是一样的#xff0c;我们都用队列#xff0c;一层一层的指。前n-1个都指向其队列后面的元素。
1.2代码及注释
typed… 题目链接/文章讲解/视频讲解 代码随想录 1.117.填充每个节点的下一个右侧节点指针II
1.1分析及思路
和116.填充每个节点的下一个右侧节点指针是一样的我们都用队列一层一层的指。前n-1个都指向其队列后面的元素。
1.2代码及注释
typedef struct Node ElemType; // 定义结构体 Node 为 ElemType
#define MaxSize 6001 // 定义队列的最大容量为 6001typedef struct {ElemType* data[MaxSize]; // 存储元素的数组int size; // 队列当前元素个数int front, rear; // 队列头尾指针
} SqQueue;void InitQueue(SqQueue* Queue) {Queue-rear Queue-front 0; // 初始化队列头尾指针Queue-size 0; // 初始化队列元素个数为 0
}bool isEmpty(SqQueue Queue) {if (Queue.rear Queue.front) // 判断队列是否为空return true;return false;
}bool GetTopQueue(SqQueue Queue, ElemType** x) {if ((Queue.size 0) || (Queue.rear Queue.front)) // 判断队列是否为空或已满return false;*x Queue.data[Queue.front]; // 获取队首元素return true;
}bool EnQueue(SqQueue* Queue, ElemType* x) {if ((Queue-rear 1) % MaxSize Queue-front) // 判断队列是否已满return false;Queue-data[Queue-rear] x; // 入队Queue-rear (Queue-rear 1) % MaxSize; // 更新 rear 指针Queue-size; // 更新队列元素个数return true;
}bool DeQueue(SqQueue* Queue, ElemType** data) {if ((Queue-size 0) || (Queue-rear Queue-front)) // 判断队列是否为空return false;*data (*Queue).data[Queue-front]; // 出队Queue-front (Queue-front 1) % MaxSize; // 更新 front 指针Queue-size--; // 更新队列元素个数return true;
}struct Node* connect(struct Node* root) {if(root NULL) // 判断根节点是否为空return NULL;SqQueue Queue; // 定义队列InitQueue(Queue); // 初始化队列EnQueue(Queue,root); // 根节点入队while(!isEmpty(Queue)){ // 遍历队列中的节点int QueueLen Queue.size; // 获取当前队列长度struct Node* Node NULL; // 定义节点指针for(int i0;iQueueLen;i){ // 遍历当前队列中的节点DeQueue(Queue,Node); // 出队一个节点if (i QueueLen - 1) // 如果不是最后一个节点Node-next Queue.data[Queue.front]; // 直接连接下一个节点if(Node-left ! NULL) // 如果左子节点不为空EnQueue(Queue,Node-left); // 左子节点入队if(Node-right ! NULL) // 如果右子节点不为空EnQueue(Queue,Node-right); // 右子节点入队}}return root; // 返回根节点
}2.104.二叉树的最大深度
2.1分析及思路
与上几个题目类似这个就相当于求的是层数有几层就是就是树的深度。
2.2代码及注释
typedef struct Node ElemType; // 定义结构体 Node 为 ElemType
#define MaxSize 10001 // 定义队列的最大容量为 10001typedef struct {ElemType* data[MaxSize]; // 存储元素的数组int size; // 队列当前元素个数int front, rear; // 队列头尾指针
} SqQueue;void InitQueue(SqQueue* Queue) {Queue-rear Queue-front 0; // 初始化队列头尾指针Queue-size 0; // 初始化队列元素个数为 0
}bool isEmpty(SqQueue Queue) {if (Queue.rear Queue.front) // 判断队列是否为空return true;return false;
}bool GetTopQueue(SqQueue Queue, ElemType** x) {if ((Queue.size 0) || (Queue.rear Queue.front)) // 判断队列是否为空或已满return false;*x Queue.data[Queue.front]; // 获取队首元素return true;
}bool EnQueue(SqQueue* Queue, ElemType* x) {if ((Queue-rear 1) % MaxSize Queue-front) // 判断队列是否已满return false;Queue-data[Queue-rear] x; // 入队Queue-rear (Queue-rear 1) % MaxSize; // 更新 rear 指针Queue-size; // 更新队列元素个数return true;
}bool DeQueue(SqQueue* Queue, ElemType** data) {if ((Queue-size 0) || (Queue-rear Queue-front)) // 判断队列是否为空return false;*data (*Queue).data[Queue-front]; // 出队Queue-front (Queue-front 1) % MaxSize; // 更新 front 指针Queue-size--; // 更新队列元素个数return true;
}int maxDepth(struct TreeNode* root) {// 初始化高度为 0int high 0;// 如果根节点为空返回高度为 0if(root 0)return high;// 定义一个队列和相关变量SqQueue Queue;int QueueLen 0;struct TreeNode* Node;// 初始化队列并将根节点入队InitQueue(Queue);EnQueue(Queue,root);// 循环直到队列为空while(!isEmpty(Queue)){// 获取当前队列的长度QueueLen Queue.size;// 遍历当前队列中的节点for(int i0;iQueueLen;i){// 出队一个节点DeQueue(Queue,Node);// 如果节点的左子树不为空将左子树入队if(Node-left ! NULL)EnQueue(Queue,Node-left);// 如果节点的右子树不为空将右子树入队if(Node-right ! NULL)EnQueue(Queue,Node-right);}// 更新高度high;}// 返回最终高度return high;
}3.111.二叉树的最小深度
3.1分析及思路
运用层序遍历当遇到一个结点左右孩子都没有时则说明该结点的深度就是最小深度只需加一个判断即可。
3.2代码及注释
typedef struct Node ElemType; // 定义结构体 Node 为 ElemType
#define MaxSize 10001 // 定义队列的最大容量为 10001typedef struct {ElemType* data[MaxSize]; // 存储元素的数组int size; // 队列当前元素个数int front, rear; // 队列头尾指针
} SqQueue;void InitQueue(SqQueue* Queue) {Queue-rear Queue-front 0; // 初始化队列头尾指针Queue-size 0; // 初始化队列元素个数为 0
}bool isEmpty(SqQueue Queue) {if (Queue.rear Queue.front) // 判断队列是否为空return true;return false;
}bool GetTopQueue(SqQueue Queue, ElemType** x) {if ((Queue.size 0) || (Queue.rear Queue.front)) // 判断队列是否为空或已满return false;*x Queue.data[Queue.front]; // 获取队首元素return true;
}bool EnQueue(SqQueue* Queue, ElemType* x) {if ((Queue-rear 1) % MaxSize Queue-front) // 判断队列是否已满return false;Queue-data[Queue-rear] x; // 入队Queue-rear (Queue-rear 1) % MaxSize; // 更新 rear 指针Queue-size; // 更新队列元素个数return true;
}bool DeQueue(SqQueue* Queue, ElemType** data) {if ((Queue-size 0) || (Queue-rear Queue-front)) // 判断队列是否为空return false;*data (*Queue).data[Queue-front]; // 出队Queue-front (Queue-front 1) % MaxSize; // 更新 front 指针Queue-size--; // 更新队列元素个数return true;
}int minDepth(struct TreeNode* root) {// 初始化高度为 0int high 0;// 如果根节点为空返回高度为 0if(root 0)return high;// 定义一个队列和相关变量SqQueue Queue;int QueueLen 0;struct TreeNode* Node;// 初始化队列并将根节点入队InitQueue(Queue);EnQueue(Queue,root);// 循环直到队列为空while(!isEmpty(Queue)){// 获取当前队列的长度QueueLen Queue.size;// 遍历当前队列中的节点for(int i0;iQueueLen;i){// 出队一个节点DeQueue(Queue,Node);// 如果节点的左子树不为空将左子树入队if(Node-left ! NULL)EnQueue(Queue,Node-left);// 如果节点的右子树不为空将右子树入队if(Node-right ! NULL)EnQueue(Queue,Node-right);// 当遇到叶子结点时就退出循环if((Node-right NULL) (Node-left NULL))break;}// 更新高度high;//遇到叶子结点就说明该高度就是最小高度if((Node-right NULL) (Node-left NULL))break;}// 返回最终高度return high;
}
如有错误还请指正若有疑问还请评论。
