LeetCode———144—— 二叉树的前序遍历

小李很执着

发布于 2024-06-15 08:56:58

760

发布于 2024-06-15 08:56:58

文章被收录于专栏：学习笔记

1.题目

. - 力扣（LeetCode）

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

2.解答

前序遍历是一种二叉树遍历方式，按照“根-左-右”的顺序访问每个节点。

1.首先计算二叉树的节点个数：

计算空间大小

int TreeSize( struct TreeNode* root)//二叉树树结点个数
{
	return root == NULL ? 0 :
		TreeSize(root->left) + TreeSize(root->right) + 1;
}

2.以先序遍历（Preorder Traversal）的方式遍历一个二叉树，并将遍历到的节点的值存储在一个整数数组中

void preorder(struct TreeNode* root,int *a,int *pi)
{
    if(root==NULL)
    return;
    a[(*pi)++]=root->val;
    preorder(root->left,a,pi);
    preorder(root->right,a,pi);

}

下面是一个简单的示例图，展示了如何对一个简单的二叉树执行先序遍历，并使用这个函数将遍历结果存储在数组中：二叉树： 1 / \ 2 3 / \ 4 5 遍历顺序：1 -> 2 -> 4 -> 5 -> 3 数组 a（假设其大小足够大）：[1, 2, 4, 5, 3] 在这个示例中，`pi` 的初始值应该是0，表示数组 `a` 的起始位置。在遍历过程中，`pi` 的值会随着节点的遍历而递增，确保每个节点的值都被存储在数组的下一个位置。

3.最终代码

preorderTraversal函数调用TreeSize函数获取节点个数，创建结果数组a，调用preorder函数进行先序遍历，并返回遍历结果数组。

需要注意的是，函数preorderTraversal返回的结果数组是动态分配的内存空间，需要在使用完毕后手动释放，以防止内存泄漏。

int TreeSize( struct TreeNode* root)//二叉树树结点个数
{
	return root == NULL ? 0 :
		TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder(struct TreeNode* root,int *a,int *pi)
{
    if(root==NULL)
    return;
    a[(*pi)++]=root->val;
    preorder(root->left,a,pi);
    preorder(root->right,a,pi);

}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
   int n=TreeSize(root);
   int *a=(int*)malloc(sizeof(int)*n);
   *returnSize=n;
   int i=0;
   preorder(root,a,&i);
   return a;
    
}