1.题目介绍
给你二叉树的根节点
root，返回它节点值的 前序 遍历。
2.实例演示
3.解题思路
本道题的意思要将前序遍历的结果储存在一个数组中，而这个数组需要动态开辟，那么这里就牵扯到数组开多大的空间？要想知道数组开多大的空间那么就需要知道二叉树有多少个结点，因此我们首先要求出二叉树的结点个数。
#二叉树结点个数
关于如何求二叉树的结点的个数在这篇博文中有过介绍：二叉树的链式结构
求二叉树结点个数的主要思想：左右子树结点个数 + 1
代码演示：
/** * 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(). */ //计算二叉树的结点个数 //节点个数 = 左右子树节点个数 + 1（根节点） int BTreeSize(struct TreeNode* root) { if(root == NULL) { return 0; } return BTreeSize(root->left) + BTreeSize(root->right) + 1; } int* preorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = BTreeSize(root); //创建数组 //...... }
#将二叉树结点的值保存在数组中
先对二叉树进行前序遍历：根节点、左子树、右子树，然后将根节点的值保存在数组中，再进行左右子树的递归，这里要注意的是：需要从外部传进来一个下标的指针，如果在函数内部设置下标，那么每一次函数递归调用就会创建新的下标，这样子只能保存第一个结点，如果从外部传的是地址，那么每一次函数递归调用就会去访问这块地址，这样就确保了不会重复保存。
完整代码：
/** * 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(). */ //计算二叉树的结点个数 //节点个数 = 左右子树节点个数 + 1（根节点） int BTreeSize(struct TreeNode* root) { if(root == NULL) { return 0; } return BTreeSize(root->left) + BTreeSize(root->right) + 1; } //前序遍历 //将前序遍历的结果保存在一个数组里面 void _preorderTraversal(struct TreeNode* root, int* pa, int* pi) { //判断是否为空树 if(root == NULL) return; //若不为空则将根节点保存至数组中 pa[*pi] = root->val; (*pi)++; //继续递归遍历它的左右子树 _preorderTraversal(root->left, pa, pi); _preorderTraversal(root->right, pa, pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = BTreeSize(root); //创建数组 //根据二叉树的结点个数来创建数组的大小 int* a = (int*)malloc(sizeof(int) * (*returnSize)); //创建数组下标 int i = 0; _preorderTraversal(root, a, &i); //返回前序遍历结果 return a; }
朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！
