【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)

作者 : admin 本文共2113个字,预计阅读时间需要6分钟 发布时间: 2024-05-23 共3人阅读

🎁个人主页:我们的五年

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

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

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(1) 

目录

1.题目描述:​编辑

2.问题分析:

🍔函数解读:

🍔确定数组的大小:

🍔调用遍历函数:

3.最终代码:


 

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

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

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

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

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

这里我们讲二叉树的前序遍历。力扣题目链接:. – 力扣(LeetCode)

1.题目描述:
【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(2)

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。

🍔确定数组的大小:

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

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(3)

题中说了节点数目在[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;

}

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(4)

测试用例过了一半,在哪个测试用例就过不了呢?

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(5)

运行测试用例都能过

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(6)

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(7)

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(8)

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

【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)插图(9)

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

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;
}

本站无任何商业行为
个人在线分享-虚灵IT资料分享 » 【二叉树】LeetCode.144:二叉树的前序遍历(小细节把握)
E-->