leetcode 144. 二叉树的前序遍历

2023-12-13 23:52:17

?这里面有一个知识点我没有详细讲(求节点个数),大概我后期会讲一下,先了解这题思路即可


144. 二叉树的前序遍历

题目

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

题目链接

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文字 和 画图 分析

  1. 分析参数代表的实际意义

?

? ? ?2. 思考递归结束条件和进行条件

这题的递归结束条件和进行条件都很明显:

遇到空树结束条件,否则进行

? ? ?3. 做题遇到的问题

问题一:局部变量销毁还传它的地址

这里明显需要把数据放入一个数组里面,然而从给出的参数来看,并没传数组的地址,由此可知,需要我们自己创建数组,由于数组是在函数内部创建的,出了作用域就销毁,所以这里的数组我们应该动态开辟,把它放在堆区

问题二:开辟空间大小的问题

由于我们需要数组存值,必须先开辟好一块空间,由于不知节点的个数,无法确定数组元素的个数,就没有办法准确开辟空间的大小,所以我们需要写一个函数,计算节点的个数

问题三:数组下标多次重复的问题

从题目意思知道,这里需要用前序,这样我们需要去递归一下,找到对应的节点的数值,把它放到数组里面,但是如果只是单纯每放完一个,数组下标加加,这里就出现问题了

我们知道,每次递归结束,就会回到上一个函数,就非常可能会发生有两次调用的函数里面的数组下标是一样的

我们这里有两种方法:(推荐第一种)

第一种:传入的是下标的地址(给的函数的参数没有这个,需要自己再创建一个函数),通过地址改变里面的下标值(因为递归时,下标的地址不会受任何影响)

第二种:定义全局变量,这样就不会收递归的影响,但是每次调用完后,必须让全局变量从 0 开始(因为第二次调用时,全局变量还是上一次调用函数留下的值)


代码

代码1(第一种方法实现)

int rootsize(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return 1 + rootsize(root->left) + rootsize(root->right);

}
int *_preorderTraversal(struct TreeNode* root, int *pa,int* pi) 
{
    if(root == NULL)
    {
        return NULL;
    }
   *(pa + *pi) = root->val;
   (*pi)++;
   _preorderTraversal(root->left, pa,pi);
   _preorderTraversal(root->right, pa,pi);
   return pa;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
   int i = 0;
   *returnSize = rootsize(root);
   int *pa = (int *)malloc(sizeof(int) *  *returnSize);
   int *pb = _preorderTraversal(root, pa,&i) ;
    return pb;
}

?

代码2(第二种方法实现)

int i = 0;
int rootsize(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return 1 + rootsize(root->left) + rootsize(root->right);

}
int *_preorderTraversal(struct TreeNode* root, int *pa) 
{
    if(root == NULL)
    {
        return NULL;
    }
   *(pa + i) = root->val;
   i++;
   _preorderTraversal(root->left, pa);
   _preorderTraversal(root->right, pa);
   return pa;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
   *returnSize = rootsize(root);
   int *pa = (int *)malloc(sizeof(int) *  *returnSize);
   int *pb = _preorderTraversal(root, pa) ;
   i = 0;
    return pb;
}

文章来源:https://blog.csdn.net/2301_79789645/article/details/134984585
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。