LeetCode———144—— 二叉树的前序遍历

简介: LeetCode———144—— 二叉树的前序遍历

1.题目


. - 力扣(LeetCode)


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


示例 1:

image.png



输入:root = [1,null,2,3]

输出:[1,2,3]

示例 2:


输入:root = []

输出:[]

示例 3:


输入:root = [1]

输出:[1]


示例 4:

image.png


输入:root = [1,2]

输出:[1,2]


示例 5:

image.png


输入:root = [1,null,2]

输出:[1,2]

提示:


树中节点数目在范围 [0, 100] 内

-100 <= Node.val <= 100

2.解答


前序遍历是一种二叉树遍历方式,按照“根-左-右”的顺序访问每个节点。


1.首先计算二叉树的节点个数:

计算空间大小


int TreeSize( struct TreeNode* root)//二叉树树结点个数
{
  return root == NULL ? 0 :
  TreeSize(root->left) + TreeSize(root->right) + 1;
}

2.以先序遍历(Preorder Traversal)的方式遍历一个二叉树,并将遍历到的节点的值存储在一个整数数组中

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

下面是一个简单的示例图,展示了如何对一个简单的二叉树执行先序遍历,并使用这个函数将遍历结果存储在数组中:


二叉树:

     1

    / \

   2   3

  / \

 4   5


遍历顺序:1 -> 2 -> 4 -> 5 -> 3


数组 a(假设其大小足够大):[1, 2, 4, 5, 3]


在这个示例中,`pi` 的初始值应该是0,表示数组 `a` 的起始位置。在遍历过程中,`pi` 的值会随着节点的遍历而递增,确保每个节点的值都被存储在数组的下一个位置。


3.最终代码

preorderTraversal函数调用TreeSize函数获取节点个数,创建结果数组a,调用preorder函数进行先序遍历,并返回遍历结果数组。


需要注意的是,函数preorderTraversal返回的结果数组是动态分配的内存空间,需要在使用完毕后手动释放,以防止内存泄漏。


int TreeSize( struct TreeNode* root)//二叉树树结点个数
{
  return root == NULL ? 0 :
  TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder(struct TreeNode* root,int *a,int *pi)
{
    if(root==NULL)
    return;
    a[(*pi)++]=root->val;
    preorder(root->left,a,pi);
    preorder(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
   int n=TreeSize(root);
   int *a=(int*)malloc(sizeof(int)*n);
   *returnSize=n;
   int i=0;
   preorder(root,a,&i);
   return a;
   
}

image.png

相关文章
|
10天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
5天前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
5天前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
5天前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
9天前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
9天前
|
算法 数据可视化 数据挖掘
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
|
10天前
|
存储 缓存 算法
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
|
5天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积