数据结构 ——— 链式二叉树oj题：将链式二叉树的前序遍历存放在数组中

题目要求

给你二叉树的根节点 root ，返回它节点值的前序遍历

手搓一个链式二叉树

代码演示：

// 数据类型
typedef int BTDataType;// 二叉树节点的结构
typedef struct BinaryTreeNode
{BTDataType data; //每个节点的数据struct BinaryTreeNode* left; //指向左子树的指针struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;// 申请新节点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));// 判断是否申请成功if (newnode == NULL){perror("malloc fail");return NULL;}// 初始化newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}// 手搓一个链式二叉树
BTNode* CreatBinaryTree1()
{BTNode* n1 = BuyNode(1);assert(n1);BTNode* n2 = BuyNode(2);assert(n2);BTNode* n3 = BuyNode(3);assert(n3);BTNode* n4 = BuyNode(4);assert(n4);BTNode* n5 = BuyNode(5);assert(n5);BTNode* n6 = BuyNode(6);assert(n6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;
}

代码实现

代码演示：

// 节点总个数
int BTreeSize(BTNode* root)
{if (root == NULL)return 0;return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}// 前序递归遍历，存入a数组
void _preorderTraversal(BTNode* root, int* a, int* pi)
{if (root == NULL)return;// 根 -> 左子树 -> 右子树a[(*pi)++] = root->data;_preorderTraversal(root->left, a, pi);_preorderTraversal(root->right, a, pi);
}// 确定returnSize的大小，定义a数组
int* preorderTraversal(BTNode* root, int* returnSize)
{// 求出节点总个数*returnSize = BTreeSize(root);// 动态开辟数组int* a = (int*)malloc(*returnSize * sizeof(int));// 判断是否开辟成功if (a == NULL){perror("malloc fail");return NULL;}int i = 0;_preorderTraversal(root, a, &i);return a;
}

代码解析：

利用 BTreeSize 函数求出节点总个数，来确定 returnSize 的大小
再定义 _preorderTraversal 函数进行前序递归遍历存储二叉树的数据到a数组中，需要注意的是，每个栈帧中 i 都是独立的，所以需要传递 i 的地址进行存储

代码验证：