前言
今天为大家带来的题均来自力扣,链接如下:
1.二叉树前序遍历
2.二叉树中序遍历
3.二叉树后续遍历
4.二叉树层序遍历
只要完全吃透这5道题,二叉树就可以轻松入门了
一、前序遍历
题目要求：
前序遍历顺序为：根-左子树-右子树
代码如下：
void DST(struct TreeNode* root,int* ret,int* returnSize)
{
if(root==NULL)
{
return;
}
ret[*returnSize] = root->val;
(*returnSize)++;
DST(root->left,ret,returnSize);
DST(root->right,ret,returnSize);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize = 0;
int* ret = (int*)malloc(sizeof(int)*2000);
DST(root,ret,returnSize);
return ret;
}
二、中序遍历
题目要求：
中序遍历:左子树-根-右子树
代码如下：
void DST(struct TreeNode* root,int* ret,int*returnSize)
{
if(root==NULL)
{
return;
}
DST(root->left,ret,returnSize);
ret[(*returnSize)++] = root->val;
DST(root->right,ret,returnSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
int* ret = (int*)malloc(sizeof(int)*200);
*returnSize = 0;
DST(root,ret,returnSize);
return ret;
}
三、后续遍历
题目要求：
后续遍历顺序:左子树-右子树-根
代码如下：
void DST(struct TreeNode* root,int* ret,int* returnSize)
{
if(root==NULL)
{
return;
}
DST(root->left,ret,returnSize);
DST(root->right,ret,returnSize);
ret[(*returnSize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize = 0;
int* ret = (int*)malloc(sizeof(int)*200);
DST(root,ret,returnSize);
return ret;
}
四、层序遍历
题目要求：
层序动图如下：
二叉树的层序实现主要是运用队列来实现
代码如下：
typedef struct TreeNode* QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
//队列的结构
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
// 初始化队列
void QueueInit(Queue* q)
{
q->tail = NULL;
q->head = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
exit(-1);
}
else
{
newnode->next = NULL;
newnode->data = data;
if (q->tail == NULL)
{
q->tail = q->head = newnode;
}
else
{
q->tail->next = newnode;
q->tail = newnode;
}
}
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->tail);
if (q->head->next == NULL)
{
free(q->head);
q->head = q->tail = NULL;
}
else
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->tail);
return q->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->tail);
return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
int n = 0;
QNode* cur = q->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
return q->tail == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
assert(q->tail);
QNode* cur = q->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
free(q);
}
void QueuePrint(Queue* q)
{
QNode* cur = q->head;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
if(root==NULL)
{
*returnSize = 0;
return NULL;
}
*returnSize = 0;
Queue p;
QueueInit(&p);//初始化队列
QueuePush(&p,root);//将头结点入队列
int n = 1;
int** ret = NULL;
*returnColumnSizes = (int*)malloc(sizeof(int)*2000);
int flag = 1;
while(!QueueEmpty(&p))
{
int c = 0;
int j = 0;
int* m = (int*)malloc(sizeof(int)*n);
while(n--)
{
struct TreeNode* tmp = QueueFront(&p);
if(tmp->left)
{
QueuePush(&p,tmp->left);
c++;
}
if(tmp->right)
{
QueuePush(&p,tmp->right);
c++;
}
if(flag==1)
{
m[j++] = tmp->val;
}
else
{
m[n] = tmp->val;
j++;
}
QueuePop(&p);
}
(*returnSize)++;
(*returnColumnSizes)[*returnSize-1] = j;
ret = (int**)realloc(ret,sizeof(int*)*(*returnSize));
ret[*returnSize-1] = m;
n = c;
flag*=-1;
}
return ret;
}
总结
以上就是二叉树遍历的全部内容希望对大家能够有所帮助
