当前位置：首页 > news >正文

leetcode 513.找树左下角的值

news 来源：原创 2024/9/20 23:21:57

1.题目要求:
代码块:

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。

在这里插入图片描述
2.此题思路:
1.创建队列，出队函数和入队函数:

//创建队列
typedef struct queuet{struct TreeNode* value;struct queue* next;
}queue_t;
//入队
void push(queue_t** head,struct TreeNode* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->value = data;newnode->next = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
//出队
struct TreeNode* pop(queue_t** head){struct TreeNode* x = (*head)->value;(*head) = (*head)->next;return x;
}

2.创建两个数组，一个用于层序遍历，一个用于记录树每层的结点个数:

queue_t* enquence = NULL;int size = 0;int count = 1;//当前行的结点数int nextcount = 0;//记录树下一行的结点数int* number = (int*)malloc(sizeof(int) * 10000);//用来层序遍历int j1 = 0;int* low = (int*)malloc(sizeof(int) * 10000);//用来记录树每层的结点个数int j2 = 0;

层序遍历:

push(&enquence,root);//入队size++;//进行层序遍历while(size != 0){ for(int i = 0;i <  count;i++){struct TreeNode* temp = pop(&enquence);//出队size--;number[j1] = temp->val;//往数组里存入结点值j1++;if(temp->left != NULL){push(&enquence,temp->left);//入队nextcount++;//此代表下一行的节点数size++;}if(temp->right != NULL){push(&enquence,temp->right);//入队nextcount++;size++;}}low[j2] = count;j2++;count = nextcount;nextcount = 0;}

4.取记录行结点数的数组的最后一个,最后让另一个数组，从后向前走，直到等于记录节点数的最后一个:

count = low[j2 - 1];int count1 = 1;for(int i = j1 - 1;i >= 0;i--){if(count1 == count){return number[i]; }count1++;}return 0;

全部代码:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*///创建队列
typedef struct queuet{struct TreeNode* value;struct queue* next;
}queue_t;
//入队
void push(queue_t** head,struct TreeNode* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->value = data;newnode->next = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
//出队
struct TreeNode* pop(queue_t** head){struct TreeNode* x = (*head)->value;(*head) = (*head)->next;return x;
}
int findBottomLeftValue(struct TreeNode* root) {queue_t* enquence = NULL;int size = 0;int count = 1;//当前行的结点数int nextcount = 0;//记录树下一行的结点数int* number = (int*)malloc(sizeof(int) * 10000);//用来层序遍历int j1 = 0;int* low = (int*)malloc(sizeof(int) * 10000);//用来记录树每层的结点个数int j2 = 0;push(&enquence,root);size++;//进行层序遍历while(size != 0){ for(int i = 0;i <  count;i++){struct TreeNode* temp = pop(&enquence);size--;number[j1] = temp->val;j1++;if(temp->left != NULL){push(&enquence,temp->left);nextcount++;size++;}if(temp->right != NULL){push(&enquence,temp->right);nextcount++;size++;}}low[j2] = count;j2++;count = nextcount;nextcount = 0;}count = low[j2 - 1];int count1 = 1;for(int i = j1 - 1;i >= 0;i--){if(count1 == count){return number[i]; }count1++;}return 0;
}