首页 > 其他分享 >二叉树-递归遍历

二叉树-递归遍历

时间:2024-04-06 17:00:23浏览次数:31  
标签:result 遍历 TreeNode cur 递归 Traversal vec 二叉树

深度优先遍历

先往深走,遇到叶子结点再往回走,分为前序遍历,中序遍历和后序遍历。方法有递归法和迭代法。前中后序遍历,指的是中间节点的遍历顺序。

前序遍历:5 4 1 2 6 7 8 中左右
中序遍历:1 4 2 5 7 6 8 左中右
后序遍历:1 2 4 7 8 6 5 左右中

深度优先遍历可利用递归法或者迭代法实现,我们先阐述递归法。

定义二叉树结点

struct TreeNode{
  int val;
  TreeNode* left;//指向左孩子
  TreeNode* right;//指向右孩子
  TreeNode(int x):val(x),left(NULL),right(NULL){}
};

实现递归算法三步:
1、确定需要输入的参数和返回值
2、确定函数的终止条件
3、确定单次递归的逻辑。

前序遍历-递归实现

class Solution{
public:
  void Traversal(TreeNode* cur, vector<int>& vec){
    if(cur == NULL) return;
    vec.push_back(cur->val);//中
    Traversal(cur->left,vec);//左
    Traversal(cur->right,vec);//右
  }
  vector<int> preorderTraversal(TreeNode* root){
    vector<int> result;
    Traversal(root,result);
    return result;
  }
};

中序遍历-递归实现

class Solution{
public:
  void Traversal(TreeNode* cur, vector<int>& vec){
    if(cur == NULL) return;
    Traversal(cur->left,vec);//左
    vec.push_back(cur->val);//中
    Traversal(cur->right,vec);//右
  }
  vector<int> preorderTraversal(TreeNode* root){
    vector<int> result;
    Traversal(root,result);
    return result;
  }
};

后序遍历-递归实现

class Solution{
public:
  void Traversal(TreeNode* cur, vector<int>& vec){
    if(cur == NULL) return;
    Traversal(cur->left,vec);//左
    Traversal(cur->right,vec);//右
    vec.push_back(cur->val);//中
  }
  vector<int> preorderTraversal(TreeNode* root){
    vector<int> result;
    Traversal(root,result);
    return result;
  }
};

标签:result,遍历,TreeNode,cur,递归,Traversal,vec,二叉树
From: https://www.cnblogs.com/perngfey-note/p/18117602

相关文章

  • 16天【代码随想录算法训练营34期】第六章 二叉树part03(● 104.二叉树的最大深度 559
    104.二叉树的最大深度#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:defmaxDepth(self,root:O......
  • 【三十五】【算法分析与设计】综合练习(2),22。 括号生成,77。 组合,494。 目标和,模拟树递
    22.括号生成数字n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。示例1:输入:n=3输出:["((()))","(()())","(())()","()(())","()()()"]示例2:输入:n=1输出:["()"]提示:1<=n<=8【三十五】【算法分析与设计】综合练习(2),......
  • LC 226.翻转二叉树
    226.翻转二叉树给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]提示:树中节点数目范围在[0,100]内......
  • 代码随想录算法训练营DAY18|C++二叉树Part.5|513.找树左下角的值、112. 路径总和、113
    文章目录513.找树左下角的值层序-迭代遍历前中后序-递归遍历思路伪代码CPP代码112.路径总和、113.路径总和II112.路径总和思路伪代码实现CPP代码113.路径总和II思路伪代码实现CPP代码实现106\105.从中(前)序与后(中)序遍历序列构造二叉树106.从中序与后序遍历序列......
  • 数据结构 第五章(树和二叉树)【下】
    写在前面:本系列笔记主要以《数据结构(C语言版)》为参考(本章部分图片以及知识点整理来源于王道),结合下方视频教程对数据结构的相关知识点进行梳理。所有代码块使用的都是C语言,如有错误欢迎指出。视频链接:第01周a--前言_哔哩哔哩_bilibili哈夫曼树部分的代码参考了一位小伙伴分享的......
  • 数据结构:二叉搜索树、平衡二叉树(AVL树)、红黑树、B树、B+树
    个人理解浅谈数据结构,应对八股文面试目录前言一、二叉搜索树(二叉排序树、二叉查找树、AVL树)(1)二叉树的特点:(2)二叉树的优缺点二、平衡二叉树(高度平衡树,最早的自平衡二叉树)(1)平衡二叉树的特点:(2)平衡二叉树的优缺点三、红黑树(1)红黑树的特点(2)红黑树的优缺点四、红黑树......
  • 数据结构:详解【树和二叉树】
    1.树的概念及结构(了解)1.1树的概念树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。1.2树的结构1.3树与非树:1.4树在实际中的运用(表示文件系统的目录树结构)2.......
  • SQL 递归核心思想(递归思维)
    目前很缺递归思维,主要是算法代码写得少,本篇记录下最近思考的内容。以PostgreSQL代码举例(主要是非常喜欢这款性能小钢炮数据库)。树状查询不多说,很简单大家基本都会,主要讲cte代码递归实现不同需求。以下所有内容都是我个人理解,不对之处请各位读者多指教!cte语法简介以PG举......
  • 图的遍历-BFS
    1.BFS遍历BFS算法的思想:对一个无向连通图,在访问图中某一起始顶点v后,由v出发,依次访问v的所有未访问过的邻接顶点w1,w2,w3,…wt;然后再顺序访问w1,w2,w3,…wt的所有还未访问过的邻接顶点;再从这些访问过的顶点出发,再访问它们的所有还未访问过的邻接顶点,……,如此直......
  • 算法分析与设计——实验1: 递归与分治
    实验一 递归与分治一、实验目的        1、理解分治算法的概念和基本要素;        2、理解递归的概念;        3、掌握设计有效算法的分治策略。二、实验内容和要求实验要求:通过上机实验进行算法实现,保存和打印出程序的运行结果,并结合程序进行......