Antecedent traversal of binary tree < difficulty coefficient ⭐ >

“This is the 25th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

📝 description: Given the root node of the binary tree, root, return a pre-traversal of its node value.

💨 Example 1:

Input: root = [1,null,2,3] output: [1, 3]

💨 Example 2:

Input: root = [] Output: []

💨 Example 3:

Input: root = [1] Output: [1]

💨 Example 4:

Input: root = [1,2] output: [2]

💨 Example 5:

Input: root = [1, NULL,2]

⚠ note:

1 the number of nodes in ️ tree is within the range [0, 100]

2️⃣ -100 <= Node.val <= 100

🧷 Platform: Visual Studio 2017 && Windows

🔑 core idea: first implement TreeSize to calculate the number of nodes in the binary tree to returnSize, and open up returnSize array of int type size. If the stack frame is empty, end the stack frame; otherwise, put the node into an array and continue recursing

Leetcode the original

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int BTDataType;
typedef struct TreeNode 
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
}BTNode;

/ / malloc space
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->val = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
/ / create a tree
BTNode* CreatBinaryTree(a)
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);

	node1->right = node2;
	node2->left = node3;

	return node1;
}

// Find the number of nodes in the binary tree
int TreeSize(struct TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// Subfunctions are used recursively - in a pre-ordered manner
void _preorderTraversal(struct TreeNode* root, int* arr, int* pi)
{
	if (root == NULL)
		return;
	/ / the node
	arr[(*pi)++] = root->val;
	_preorderTraversal(root->left, arr, pi);
	_preorderTraversal(root->right, arr, pi);
}
//Note: The returned array must be malloced, assume caller calls free().
 // The binary tree is preordered
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
	//*returnSize Specifies the number of nodes to receive the binary tree
	*returnSize = TreeSize(root);
	// create *returnSize int size space
	int* arr = (struct TreeSize*)malloc(sizeof(int)* *returnSize);
	// Since preorderTraversal is not suitable for recursion, a sub-function is required; Each recursion here is a stack of function frames, so for I to keep the correct subscript you have to pass the address
	int i = 0;
	_preorderTraversal(root, arr, &i);
	return arr;
}
int main(a)
{
	int returnSize = 0;
	BTNode* root = CreatBinaryTree();
	int* arr = preorderTraversal(root, &returnSize);
	return 0;
}
Copy the code