深圳网站设计公司哪个厦门人才网个人登录
目录
1.知识回顾
2.题目
代码模板
3.分析
数组的初始化
malloc开辟的几种方案对比
奇怪的参数returnSize
做法
代码框架
4.代码
提交结果
5.PreOrder函数常见的错误写法
1.知识回顾
106.【C语言】数据结构之二叉树的三种递归遍历方式
2.题目
https://leetcode.cn/problems/binary-tree-preorder-traversal/
给你二叉树的根节点
root，返回它节点值的 前序 遍历。示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内-100 <= Node.val <= 100进阶：递归算法很简单，你可以通过迭代算法完成吗？
代码模板
/*** 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().*/
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{}3.分析
和106.【C语言】数据结构之二叉树的三种递归遍历方式文章有所不同,LeetCode函数的返回值为int*,即返回一个不带NULL的int数组
数组的初始化
注意不可以返回局部数组!就像下面这样
//......
int a[100];
return a;
//......一旦离开preorderTraversal函数会被销毁,导致出现野指针,因此必须malloc在堆区开辟
而且LeetCode给出了提示
Note: The returned array must be malloced, assume caller calls free().这里不用担心free的问题,假设调用者调用了free()
malloc开辟的几种方案对比
方案1.LeetCode给出了提示"树中节点数目在范围 [0, 100] 内",因此可以一次性开辟足够的空间
int* a = (int*)malloc(100*sizeof(int));
但可能会出现空间浪费的情况
方案2.先计算二叉树的大小(节点个数*每个节点所占的内存空间),再malloc
方案3.一开始开辟较小的空间,不够了再扩容
本文采用方案2,直接调用107.【C语言】数据结构之二叉树求总节点和第K层节点的个数文章的TreeSize函数
奇怪的参数returnSize
在int* preorderTraversal(struct TreeNode* root, int* returnSize)传了一个int*类型的参数returnSize,
LeetCode规定返回数组时要不仅仅要求返回首元素的地址还要返回数组的大小returnSize
由于形参的改变不影响实参,因此需要传returnSize的地址,因此为int*类型的参数
做法
return a;之前先将数组的大小传给*returnSize
代码框架
int TreeSize(struct TreeNode* root)
{return root==NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize=TreeSize(root);int* a=(int*)malloc(*returnSize*sizeof(int));//......//遍历并写入数组//......return a;
}4.代码
106.【C语言】数据结构之二叉树的三种递归遍历方式文章的PreOrder函数的代码
void PreOrder(BTNode* root)
{//先判断是否为空树(叶节点的左节点和右节点均为空树)if (root == NULL){printf("NULL ");return;}//按根-->左子树-->右子树的顺序遍历printf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}稍加改造上方PreOrder函数即可
void PreOrder(struct TreeNode* root,int* a,int* i)
{if (root==NULL)return;//写入数组a[(*i)++]=root->val;PreOrder(root->left,a,i);PreOrder(root->right,a,i);
}int TreeSize(struct TreeNode* root)
{return root==NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize=TreeSize(root);int* a=(int*)malloc(*returnSize*sizeof(int));int i=0;PreOrder(root,a,&i);return a;
}提交结果
如果将代码的*returnSize=TreeSize(root);注释掉会报错
5.PreOrder函数常见的错误写法
void PreOrder(struct TreeNode* root,int* a,int i)
{if (root==NULL)return;//写入数组a[i++]=root->val;PreOrder(root->left,a,i);PreOrder(root->right,a,i);
}//省略TreeSize
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{//前面内容省略PreOrder(root,a,0);//后面内容省略
}运行结果:不完全通过
以下面这个用例分析
画递归展开图
由于CSDN会压缩图片画质,无损bmp图片(大小7.32M)链接见https://pan.baidu.com/s/1OIrE-cGvefJs_SFZ75w84w?pwd=gq37
解决方法:1.传址调用 2.使用全局变量
备注:不建议使用全局变量,LeetCode有多个测试用例会反复调用函数,导致全局变量无法清零