一:题目
解释:
1:
题目的要求就是我们return 一个数组,该数组里面的元素及其顺序就是 前序遍历二叉树 的元素及其顺序
比如:示例1的树,前序遍历的顺序应该是1 2 3,那么return 的数组里面的元素及其顺序就是1 2 3
2:
红框里的 returnSize是一个int * 类型的,是一个被传过来的整形指针,它的作用就是我们要将其赋为数组的元素个数,也就是 *returnSize = 元素个数,因为传过来的是int* ,我们才能真正的改变其本身。
returnSize并不是让我们将其当做一个变量来使用,因为变量我们可以自己创建,并不需要这么麻烦的当做参数传给我们。
3:
因为C语言不支持返回数组和数组的大小两个变量,所以通常会通过一个额外的参数来传递数组的大小。
二:代码
根据前文,可知:
1:我们要得到数组的元素个数
2:我们要把前序遍历的元素及其顺序放进数组中
3:最后返回这个数组,且将returnSize赋成元素的个数
解释:
第一个函数 (int TreeSize(struct TreeNode* root)
)
1:
int TreeSize(struct TreeNode* root)
:
- 这是一个函数定义,名为
TreeSize
,它接收一个指向二叉树节点的指针root
作为参数。 - 函数返回一个整数,这个整数代表了以
root
为根的整棵二叉树中的节点数量。
2:
return root==NULL? 0:TreeSize(root->left)+TreeSize(root->right)+1;
:
- 这是函数的返回语句,使用了条件运算符(也称为三元运算符)。
root==NULL
:检查传入的节点是否为空(即检查树是否为空或者是否到达了叶节点的子节点)。- 如果
root
为NULL
(意味着当前子树为空),则返回0
,因为空树没有节点。 - 如果
root
不为NULL
,则递归计算左子树和右子树的节点数量,并将它们相加,然后加上当前节点(root
),因此是TreeSize(root->left) + TreeSize(root->right) + 1
。
3:
递归的工作原理如下:
- 递归的基本情况(停止条件):当递归到叶子节点的子节点时(即遇到
NULL
),返回0
。 - 递归的递推情况:对于非空的树,函数递归地计算左子树和右子树的大小,将这两个值相加,并加上当前节点(
root
)本身。
递归最终会遍历二叉树中的每一个节点,并将它们全部计数一次。
4:
一种错的书写方式:
原因:表达式能用在三目中,而语句不能。return 0 这是一个语句,而0是一个表达式。
第二个函数(void preorder(struct TreeNode* root,int * arr,int* pi))
代码解释:
-
void preorder(struct TreeNode* root, int * arr, int* pi)
:- 定义了一个名为
preorder
的函数,它接收三个参数:struct TreeNode* root
:当前遍历到的二叉树节点的指针。int * arr
:一个整数数组的指针,用于存储遍历的结果。int* pi
:一个整数指针,用于跟踪当前应该将节点值放入数组的哪个位置。
- 定义了一个名为
-
if(root==NULL) return;
:- 这是递归的基本情况(停止条件)。如果当前节点是
NULL
(即到达了叶子节点的子节点),则直接返回,不执行任何操作。
- 这是递归的基本情况(停止条件)。如果当前节点是
-
arr[(*pi)++] = root->val;
:- 将当前节点
root
的值root->val
存储到数组arr
的第(*pi)
个位置,并将pi
指向的索引值自增1。这里的(*pi)++
是一个后缀自增运算符,它首先返回*pi
的值,然后将*pi
的值加1。
- 将当前节点
-
preorder(root->left, arr, pi);
:- 递归调用
preorder
函数来遍历当前节点的左子树。
- 递归调用
-
preorder(root->right, arr, pi);
:- 递归调用
preorder
函数来遍历当前节点的右子树。
- 递归调用
Q:j是用来控制下标的,那为什么穿的不是j,而是&j?
A:
可知:
在第9步之前pi都是3,但是第9步之后,他回到了上一层函数,这层函数里面的pi是1++之后的2,所以pi被改变了,指向了错误的位置,如果后面还有新的节点要存进数组,3这个值就会被覆盖,而&j就避免了这种错误,不管在哪一层,他的值都是被全局改变了
第三个函数:preorderTraversal
就是结合前两个函数,用第一个函数的返回值得到n,n就能malloc一个刚刚好大小的数组,然后再传给preorder 函数将数组按照前序遍历装满,最后将n给returnSize,最后return arr数组。
关于前中后序遍历不了解的同学:递归实现 前/中/后序 遍历二叉树 的详细讲解-CSDN博客
中序:
后序: