用C语言实现:给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值
时间: 2023-10-20 14:46:39 浏览: 100
leetcodetreenode-LeetCode---Symmetric-Tree:给定一棵二叉树,检查它是否是自身的镜像(即围绕其中心对称
要按照从右侧所能看到的节点值的顺序遍历二叉树,可以使用广度优先搜索(BFS)的方法。具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 定义队列节点结构
struct QueueNode {
struct TreeNode *treeNode;
struct QueueNode *next;
};
// 入队操作
void enqueue(struct QueueNode **front, struct QueueNode **rear, struct TreeNode *treeNode) {
struct QueueNode *newNode = (struct QueueNode *)malloc(sizeof(struct QueueNode));
newNode->treeNode = treeNode;
newNode->next = NULL;
if (*front == NULL) {
*front = *rear = newNode;
} else {
(*rear)->next = newNode;
*rear = newNode;
}
}
// 出队操作
struct TreeNode *dequeue(struct QueueNode **front, struct QueueNode **rear) {
if (*front == NULL) {
return NULL;
}
struct QueueNode *temp = *front;
struct TreeNode *treeNode = temp->treeNode;
if (*front == *rear) {
*front = *rear = NULL;
} else {
*front = (*front)->next;
}
free(temp);
return treeNode;
}
// 获取从右侧所能看到的节点值
int* rightSideView(struct TreeNode* root, int* returnSize) {
if (root == NULL) {
*returnSize = 0;
return NULL;
}
int* result = (int*)malloc(sizeof(int));
struct QueueNode *front = NULL;
struct QueueNode *rear = NULL;
struct TreeNode *node;
int levelSize;
enqueue(&front, &rear, root);
while (front != NULL) {
levelSize = rear - front + 1;
result = (int*)realloc(result, (*returnSize + levelSize) * sizeof(int));
for (int i = 0; i < levelSize; i++) {
node = dequeue(&front, &rear);
result[(*returnSize)++] = node->val;
if (node->left != NULL) {
enqueue(&front, &rear, node->left);
}
if (node->right != NULL) {
enqueue(&front, &rear, node->right);
}
}
}
return result;
}
// 创建二叉树节点
struct TreeNode* createTreeNode(int value) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
// 创建示例二叉树
struct TreeNode* root = createTreeNode(1);
root->left = createTreeNode(2);
root->right = createTreeNode(3);
root->left->right = createTreeNode(5);
root->right->right = createTreeNode(4);
int returnSize;
int* result = rightSideView(root, &returnSize);
printf("从右侧所能看到的节点值为:");
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
free(result);
return 0;
}
```
在这段代码中,我们定义了 `struct TreeNode` 结构来表示二叉树节点,其中包含一个 `val` 域表示节点的值,以及左右子节点的指针。我们还定义了 `struct QueueNode` 结构来表示队列节点,其中包含一个指向二叉树节点的指针以及下一个节点的指针。
在 `enqueue()` 函数中,我们通过创建新节点并将其插入队列的尾部来实现入队操作。在 `dequeue()` 函数中,我们从队列的头部取出节点并返回。
`rightSideView()` 函数使用 BFS 遍历二叉树,并将从右侧所能看到的节点值保存在动态数组 `result` 中。我们使用队列来辅助进行 BFS 遍历,将根节点入队,然后在每一层遍历时依次将每个节点的左右子节点入队。最后,我们将每层最右侧的节点值保存在 `result` 数组中。
在 `main()` 函数中,我们创建了一个示例二叉树,并调用 `rightSideView()` 函数获取从右侧所能看到的节点值,并输出结果。
注意:在使用完动态数组 `result` 后需要使用 `free()` 函数释放内存。
阅读全文