【二叉树】LeetCode.144：二叉树的前序遍历（小细节把握）

🎁个人主页：我们的五年

🔍系列专栏：初阶初阶结构刷题

🎉欢迎大家点赞👍评论📝收藏⭐文章

前言：
二叉树的遍历顺序有：

1.前序：根->左子树->右子树。

2.中序：左子树->根->右子树。

3.后序：左子树->右子->树。

4.层序：一层一层的遍历。

这里我们讲二叉树的前序遍历。力扣题目链接：. - 力扣（LeetCode）

1.题目描述：

2.问题分析：

🍔函数解读：

力扣官方给的函数接口：

int* preorderTraversal(struct TreeNode* root, int* returnSize) {

}

returnSize是数组的长度的地址，不是数组首地址。

而且前面还有这样一句话： ***** Note: The returned array must be malloced, assume caller calls free().

也就是说，还要malloc动态在堆区上申请一个数组，这样preorderTraversal这个函数销毁时，数组不随函数一起销毁，因为数组在堆区上。而且我们也不要去free（），由caller去free。

🍔确定数组的大小：

我们要去申请数组，那就要确定数组的大小，那么我们把数组的大小顶为多大呢？

题中说了节点数目在[0,100]。

📷给出下面几种情况进行选择：（看看哪种情况最好）

1.因为题目中给了最多为100个节点，所以申请100*sizeof（int）的大小？

2.先申请小一点，不够的话就再去扩容？

3.先去计算树的大小，再去扩容？

分析：

1.如果题目给的是一亿个，我们不可能去申请一亿大小的空间。而且这种情况会有空间浪费。

2.如果频繁的扩容会造成速度很慢，特别是异地扩容，realloc内部自己还要去移动数据。

3.情况三不会浪费空间，又不会频繁扩容。

所以我们先去计算树的节点个数：

分治思想：每次都把树分成三个部分，根+左子树+右子树

最小子问题根为NULL就返回0.

 int TreeSize(struct TreeNode* root)
 {
    if(root==NULL)
        return 0;
    //分治，总个数等于根+加左子树的个数+右子树的个数
    return TreeSize(root->left)+TreeSize(root->right)+1;
 }

🍔调用遍历函数：

//i的作用是确定调用该函数的时候，在哪个位置插入。

并且传指针，（*i）++才能改变外部i的值。

如果是传值，i的值不能改变，同一个函数里面左子树i和右子树一样。下面右具体分析：

void preorder(struct TreeNode* root,int* a,int* i)

{

if(root==NULL)

    return;

a[(*i)++]=root->val;

preorder(root->left,a,i);

preorder(root->right,a,i);

}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {

*returnSize=TreeSize(root);

int *a=(int*)malloc(sizeof(int)*(*returnSize));

int i=0;

preorder(root,a,&i);

return a;

}

测试用例过了一半，在哪个测试用例就过不了呢？

运行测试用例都能过

如果细心一点的就可以发现，左右子树都有的时候，就过不了，只有一边有树，或者只有根就可以过。

因为这样左右子树开始时都是一样的，如果这样，调用右边的时候，又把左边已经覆盖的值又去覆盖了一遍，所以左边子树的值就没了。

3.最终代码：

/**
 * 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().
 */
 int TreeSize(struct TreeNode* root)
 {
    if(root==NULL)
        return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
 }

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

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