给你二叉树的根节点 root ,返回它节点值的先序遍历,用C语言写出完整代码来,并且有思路说明和相关注释
时间: 2024-02-13 10:04:11 浏览: 71
思路说明:
先序遍历二叉树的顺序是先访问根节点,然后是左子树,最后是右子树。因此,我们可以采用递归的方式来实现先序遍历。
具体实现时,我们先访问根节点,并将其值存入结果数组中,然后递归遍历左子树和右子树。
代码实现:
```c
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void preorderTraversalHelper(struct TreeNode* root, int* returnSize, int* result) {
if (!root) {
return;
}
result[*returnSize] = root->val; // 访问根节点,并将其值存入结果数组中
(*returnSize)++;
preorderTraversalHelper(root->left, returnSize, result); // 递归遍历左子树
preorderTraversalHelper(root->right, returnSize, result); // 递归遍历右子树
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int* result = (int*)malloc(sizeof(int) * 100); // 初始化结果数组
*returnSize = 0;
preorderTraversalHelper(root, returnSize, result); // 递归遍历二叉树
return result;
}
```
注释说明:
- `preorderTraversalHelper` 函数是先序遍历的辅助函数,用于递归遍历二叉树。
- `result` 数组是存储遍历结果的数组,`returnSize` 是遍历结果的长度。
- 在 `preorderTraversalHelper` 函数中,先访问根节点并将其值存入结果数组中,然后递归遍历左子树和右子树。
- `preorderTraversal` 函数是主函数,用于初始化结果数组并调用 `preorderTraversalHelper` 函数遍历二叉树。
- 最后返回结果数组即可。
阅读全文