二叉树OJ题:LeetCode--144.二叉树的前序遍历

简介: 二叉树OJ题:LeetCode--144.二叉树的前序遍历



1.题目介绍

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

2.实例演示

3.解题思路

本道题的意思要将前序遍历的结果储存在一个数组中,而这个数组需要动态开辟,那么这里就牵扯到数组开多大的空间?要想知道数组开多大的空间那么就需要知道二叉树有多少个结点,因此我们首先要求出二叉树的结点个数。

#二叉树结点个数

关于如何求二叉树的结点的个数在这篇博文中有过介绍:二叉树的链式结构

求二叉树结点个数的主要思想:左右子树结点个数 + 1

代码演示:

/**
 * 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().
 */
//计算二叉树的结点个数
//节点个数 = 左右子树节点个数 + 1(根节点)
int BTreeSize(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return BTreeSize(root->left) 
         + BTreeSize(root->right) + 1;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = BTreeSize(root);
    //创建数组
    //......
}

#将二叉树结点的值保存在数组中

先对二叉树进行前序遍历:根节点、左子树、右子树,然后将根节点的值保存在数组中,再进行左右子树的递归,这里要注意的是:需要从外部传进来一个下标的指针,如果在函数内部设置下标,那么每一次函数递归调用就会创建新的下标,这样子只能保存第一个结点,如果从外部传的是地址,那么每一次函数递归调用就会去访问这块地址,这样就确保了不会重复保存。

完整代码:

/**
 * 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().
 */
//计算二叉树的结点个数
//节点个数 = 左右子树节点个数 + 1(根节点)
int BTreeSize(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return BTreeSize(root->left) 
         + BTreeSize(root->right) + 1;
}
//前序遍历
//将前序遍历的结果保存在一个数组里面
void _preorderTraversal(struct TreeNode* root, int* pa, int* pi)
{
    //判断是否为空树
    if(root == NULL)
        return;
    //若不为空则将根节点保存至数组中
    pa[*pi] = root->val;
    (*pi)++;
    //继续递归遍历它的左右子树
    _preorderTraversal(root->left, pa, pi);
    _preorderTraversal(root->right, pa, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = BTreeSize(root);
    //创建数组
    //根据二叉树的结点个数来创建数组的大小
    int* a = (int*)malloc(sizeof(int) * (*returnSize));
    //创建数组下标
    int i = 0;
    _preorderTraversal(root, a, &i);
    //返回前序遍历结果
    return a;
}

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!

目录
相关文章
|
1月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
20 2
|
1月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
16 2
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
19 0
|
1月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
14 0
|
1月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
17 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
17 0
|
1月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
16 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
57 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
114 2