首页 > 其他分享 >二叉树的递归遍历(前、中、后序)

二叉树的递归遍历(前、中、后序)

时间:2024-11-04 17:44:52浏览次数:3  
标签:遍历 TreeNode val 后序 List result root 二叉树

二叉树的递归遍历

题目链接:
前序遍历: LeetCode 144
中序遍历: LeetCode 94
后序遍历: LeetCode 145
描述
给你二叉树的根节点 root ,返回它节点值的 前序中序后序 遍历。
在这里插入图片描述
示例1:前序遍历

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

示例2:中序遍历

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

示例3:后序遍历

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

思路

这里前中后,其实指的就是中间节点的遍历顺序,只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序,就可以发现,中间节点的顺序就是所谓的遍历方式
前序遍历:中左右
中序遍历:左中右
后序遍历:左右中

二叉树的定义

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List result){
        if(root == null){
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root,result);
        return result;
    }

    public void inorder(TreeNode root, List result){
        if(root == null){
            return;
        }
        inorder(root.left,result);
        result.add(root.val);
        inorder(root.right,result);

    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root,result);
        return result;
    }

    public void postorder(TreeNode root, List list){
        if(root == null){
            return;
        }
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }
}

标签:遍历,TreeNode,val,后序,List,result,root,二叉树
From: https://blog.csdn.net/weixin_43777513/article/details/143417091

相关文章

  • 数据结构 ——— 链式二叉树的前中后序遍历递归实现
    目录前言链式二叉树示意图​编辑手搓一个链式二叉树链式二叉树的前序遍历链式二叉树的中序遍历链式二叉树的后序遍历 前言在上一章学习了链式二叉树的前中后序遍历的解析数据结构———链式二叉树的前中后序遍历解析-CSDN博客接下来要学习的是代码实现链式二叉树......
  • 【数据结构】二叉树——堆
    一、二叉树的概念与结构二叉树的概念二叉树是树的一种,二叉树的特殊之处在于,每个根节点都可以有两个子节点,可以两个子节点都为空,或者一个为空,一个不为空,或者两个都有数,在构建二叉树的节点时就可以看出:现实中的二叉树:就像这颗树,每次分叉都分出两个枝条,这就是一个二叉树......
  • 二叉树进阶-二叉搜索树
    目录1.二叉树的概念2.二叉搜索树的操作2.1二叉搜索树的结构2.2实现节点的查找(find)2.3实现增加节点(insert)2.4实现删除节点(erase)2.5析构函数2.6二叉搜索树的完整实现3.二叉搜索树的应用3.1K模型3.2KV模型4.二叉搜索树的性能分析1.二叉树的概念二叉搜索树也叫二......
  • 代码随想录算法训练营第十五天|leetcode110. 平衡二叉树、leetcode257.二叉树的所有路
    1leetcode110.平衡二叉树题目链接:110.平衡二叉树-力扣(LeetCode)文章链接:代码随想录视频链接:后序遍历求高度,高度判断是否平衡|LeetCode:110.平衡二叉树_哔哩哔哩_bilibili1.1视频看后的思路1.1.1完整的代码就是不断判断,对其数据存储,其实突然发现每道题思路真的都很像,就......
  • C++——二叉树(进阶)
    1.二叉搜索树1.1概念二叉搜索树又称二叉排序树,它或是一棵空树,又或是具有以下性质的二叉树:若它的左子树不为空,则左子树上所有节点的值都小于根节点的值若它的右子树不为空,则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二......
  • 【模板】图的存储与遍历
    图的存储与遍历直接存边法做法建立三个数组u[N],v[N],w[N],对于每一次读入的起点,出点和权值存储即可。初始化structEdge{intu,v,w;};vector<Edge>graph;存储voidadd(inta,intb,intc){ graph.push_back({a,b,c});}遍历voiddfs(intver){ if(vis[v......
  • 动态动态规划 & 全局平衡二叉树 小记
    估计这几天是正式学习ddp,所以特写笔记。DDP简介是这样一类技巧,利用广义的矩阵乘法实现单点修改权值,动态查询某个点的DP值关于矩阵乘法,广义矩阵乘法其核心思想是利用矩阵乘法具有结合律(可以使用数据结构维护)的优势序列上的Ddp先看一个例子:最大子段和,显然我们有\(f_......
  • 遍历文件夹和子文件夹,删除重复文件
    importosimporthashlibimportshutildeffile_hash(filepath):"""计算文件的MD5哈希值"""hash_md5=hashlib.md5()withopen(filepath,"rb")asf:forchunkiniter(lambda:f.read(4096),b""):......
  • 【数据结构】二叉树链式结构的实现
    1.前置说明    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研究......
  • JAVA 二叉树面试题
    @目录摘要代码Node节点main函数问题1:递归——求二叉树的最大深度问题2:求二叉树的最小深度问题3:求二叉树中节点的个数问题4:求二叉树中叶子节点的个数问题5:求二叉树中第k层节点的个数,不是求第k层叶子节点个数问题6:判断两棵树是否相同问题7:给定一个二叉树,检查它是否是镜像对称的。问......