Java 数据结构中二叉树前中后序遍历非递归的具体实现详解

2024-10-18 16:22:25

一、前序遍历

1.题目描述

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

2.输入输出示例

示例 1：

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

输出：[1,2,3]

示例2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

3.解题思路

前序遍历：根结点—左子树—右子树

1.判断额外情况，如果树为空，直接返回
2.创建一个栈用来保存右子树
3.先将根结点入栈，避免多次判断栈为空
4.取出栈顶元素（第一次为根结点），从上往下遍历最左侧路径中的每个结点
5.在遍历时判断当前结点的右子树是否为空，非空则入栈
6.遍历结束后，此时栈顶元素为前一个结点的右子树，将栈顶元素取出，将其看作一棵树，继续重复上述操作，即形成循环。

4.代码实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }

        //创建一个栈用来保存右子树
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
        s.push(root);
        //从上往下遍历最左侧路径中的每个结点，并将其右子树保存起来---栈
        while(!s.empty()||cur!=null){
            cur=s.pop();
            while(cur!=null){
                list.add(cur.val);
                if(cur.right!=null){
                    s.push(cur.right);
                }
                cur=cur.left;
            }
        }
        return list;
    }
}

二、中序遍历

1.题目描述

给定一个二叉树的根节点 root ，返回它的中序遍历。

2.输入输出示例

示例 1：

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

输出：[1,3,2]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

3.解题思路

中序遍历：左子树—根结点—右子树

1.判断额外情况，如果树为空，直接返回
2.创建一个栈用来保存结点
3.从上往下遍历最左侧路径中的每个结点，并将其保存到栈中，走到cur==null的位置
4.此时栈顶元素为最左侧路径的最后一个结点，将其加入到list并将栈顶元素移除
5.判断最后一个结点的右子树是否为空，过程和上述的过程是一样的，直接将其右子树看作一棵树，整个过程便循环起来

4.代码实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
         //从上往下遍历最左侧路径中的每个结点，并将其保存到栈中
        while(!s.empty()||cur!=null){
            while(cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            cur=s.pop();
            list.add(cur.val);
            cur=cur.right;
        }
        return list;
    }
}

三、后序遍历

1.题目描述

给定一个二叉树，返回它的后序遍历。

2.输入输出示例

示例:
输入: [1,null,2,3]
1
\
2
/
3

输出: [3,2,1]

3.解题思路

后序遍历：左子树—右子树—根结点

1.判断额外情况，如果树为空，直接返回
2.创建一个栈用来保存遍历的结点
3找出以cur为根的二叉树中最左侧的节点，并保存所经路径中的所有结点—栈
4.此时栈顶元素为最左侧路径的最后一个结点
5.先要判断最后一个结点的右子树是否为空

如果为空，直接将结点加入list，同时将栈顶元素删除
如果不为空则将右子树看作一棵树，重新进入循环判断

注意：如果按照这样，到了最后的右子树就会一直循环出不来
解决方案：
创建一个prev用来标记已经遍历过的结点，将能否编历的条件改为：top的右子树为空||top的右子树已经遍历过

4.代码实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;//用来标记刚刚遍历过的节点
        while(!s.empty()||cur!=null){
            //1.找出以cur为根的二叉树中最左侧的节点，并保存所经路径中的所有节点---栈
            while(cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            TreeNode top=s.peek();
            //top能否遍历：top的右子树为空||top的右子树已经遍历过
            if(top.right==null||top.right==prev){
                list.add(top.val);
                prev=top;
                s.pop();
            }else{
                cur=top.right;
            }
        }
        return list;
    }
}

以上就是Java 数据结构中二叉树前中后序遍历非递归的具体实现详解的详细内容，更多关于Java 数据结构的资料请关注我们其它相关文章！

JAVA二叉树的几种遍历(递归，非递归)实现

首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点.本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先序,中序,后序) 一.基本概念二叉树有5种基本形态: 注:二叉树有序树,就是说一个节点的左右节点是有大小之分的,我们通常设定为左孩子一定大于右孩子,下面的实现都是基于这个规则的.二叉树分为三种:满二叉树,完全二叉树,不完全二叉树二叉树的四种遍历:层次,先序,中序,后序首先是非递归实现上图的满二叉
Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后递归非递归遍历层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.
Java二叉树的四种遍历（递归与非递归）

目录一.先序遍历与后序遍历二.中序遍历三.层序遍历一.先序遍历与后序遍历先序遍历根节点,再遍历左子树,再遍历右子树. 后序遍历先遍历左子树,再遍历右子树,再遍历根节点. 先序遍历递归实现: public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right); } 先序遍历的非递归
java非递归实现之二叉树的前中后序遍历详解

二叉树的前中后序遍历核心思想:用栈来实现对节点的存储.一边遍历,一边将节点入栈,在需要时将节点从栈中取出来并遍历该节点的左子树或者右子树,重复上述过程,当栈为空时,遍历完成. 前序遍历 //非递归 //根左右 class Solution { public List<Integer> preorderTraversal(TreeNode root) { //用数组来存储前序遍历结果 List<Integer> list = new ArrayList<>(); i
java栈实现二叉树的非递归遍历的示例代码

一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法. 二叉树设置 class Node{ public int val; public Node left; public Node right; public Node(int v) { val=v; left=null; right=null; } } public class Main { public static void main(String[] args) { Node head =new Node(0); No
java二叉树的非递归遍历

二叉树的递归遍历比较简单,这里就不聊了.今天主要聊聊二叉树的非递归遍历,主要借助于"栈"后进先出的特性来保存节点的顺序,先序遍历和中序遍历相对来说比较简单,重点理解后序遍历. 1. 先看看节点类型: //二叉树的节点类型 private class Node{ int data; //节点值 Node leftChild; //左孩子 Node rightChild; //右孩子 public Node(int data) { this.data=data; } } 2.先序遍历. 非
java二叉树的几种遍历递归与非递归实现代码

前序(先序)遍历中序遍历后续遍历层序遍历如图二叉树: 二叉树结点结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } @Override public String toString(){ return "val: "+val; } } 访问函数 public void visit(TreeNode node){ System.out.print(
Java二叉树的四种遍历(递归和非递归)

二叉树的遍历可以分为前序.中序.后序.层次遍历. 前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中->左->右: 中序遍历,遍历节点的顺序为:左->中->右: 后序遍历,遍历节点的顺序为:左->右->中. 前序遍历递归实现 public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q
Java 数据结构中二叉树前中后序遍历非递归的具体实现详解

目录一.前序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现二.中序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现三.后序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现一.前序遍历 1.题目描述给你二叉树的根节点 root ,返回它节点值的前序遍历. 2.输入输出示例示例 1: 输入:root = [1,null,2,3] 输出:[1,2,3] 示例2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1
Java数据结构最清晰图解二叉树前中后序遍历

目录一,前言二,树 ①概念 ②树的基础概念三,二叉树 ①概念 ②两种特殊的二叉树 ③二叉树的性质四,二叉树遍历 ①二叉树的遍历 ②前序遍历 ③中序遍历 ④后序遍历五,完整代码一,前言二叉树是数据结构中重要的一部分,它的前中后序遍历始终贯穿我们学习二叉树的过程,所以掌握二叉树三种遍历是十分重要的.本篇主要是图解+代码Debug分析,概念的部分讲非常少,重中之重是图解和代码Debug分析,我可以保证你看完此篇博客对于二叉树的前中后序遍历有一个新的认识!!废话不多说,让我们学起来吧!!
C++ 非递归实现二叉树的前中后序遍历

目录二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树的前序遍历在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制.二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可. 具体步骤如下: 将左路结点入栈,入栈的同时访问左路结点. 取出栈顶结点top. 准备访问top结点的右子树. struct Tre
二叉树递归迭代及morris层序前中后序遍历详解

目录分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历方法一:广度优先搜索方法二:递归 2.前序遍历 3.中序遍历 4.后序遍历递归解法前序遍历--递归迭代解法前序遍历--迭代核心思想: 三种迭代解法的总结: Morris遍历 morris--前序遍历 morris--中序遍历 morris--后序遍历: 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历方法一:广度优先搜索 (以下解释来自leetcode官方题解) 我们可以用广度优先搜索解决这个问题. 我们可以想到最
Java语言实现非递归实现树的前中后序遍历总结

前言三种遍历的递归写法都很好写,所以总结一下非递归写法. 先贴一张图复习一下三种遍历方式就进入正文啦~ [注:本文所有代码实现中树的结点定义如下: public class Node { int val; Node left; Node right; Node parent; Node() {} Node(int val) { this.val = val; } } 1.前序遍历实现思路: 前序遍历的顺序是:根结点 -> 左孩子 -> 右孩子借助一个栈结构先将根结点压入栈,然后循环每次取
C#中托管DLL和非托管DLL的区别详解

首先解释一下,托管DLL和非托管DLL的区别.狭义解释讲,托管DLL就在Dotnet环境生成的DLL文件.非托管DLL不是在Dotnet环境生成的DLL文件. 托管DLL文件,可以在Dotnet环境通过 "添加引用" 的方式,直接把托管DLL文件添加到项目中.然后通过 Using DLL命名空间,来调用相应的DLL对象 . 非托管DLL文件,在Dotnet环境应用时,通过 DllImport 调用. C# 调用非托管DLL文件.DLL文件是用C语言编写的. 托管DLL就是能够在公共
java面试题之try中含return语句时代码的执行顺序详解

前言最近在刷java面试题偶然看到这类问题(try/finally中含有return时的执行顺序),觉得挺有意思于是小小的研究了一下,希望经过我添油加醋天马行空之后,能给你带来一定的帮助,下面来看看详细的介绍. 原题 try {} 里有一个return语句,那么紧跟在这个try后的finally {}里的代码会不会被执行?什么时候被执行?在return前还是后? 乍一看题目很简单嘛,java规范都说了,finally会在try代码块的return之前执行,你这文章写得没意义,不看了你等等!(
C#中Foreach循环遍历的本质与枚举器详解

目录前言 1.创建一个控制台应用程序 2.编写测试代码并分析 3.总结前言对于C#里面的Foreach学过语言的人都知道怎么用,但是其原理相信很多人和我一样都没有去深究.刚回顾泛型讲到枚举器让我联想到了Foreach的实现,所以进行一番探究,有什么不对或者错误的地方大家多多斧正. 1.创建一个控制台应用程序 2.编写测试代码并分析在Program类中写一个foreach循环 class Program { static void Main(string[] args) { List p
C语言中二叉树的后序遍历详解

目录一.二叉树的后序遍历.(递归) 二.二叉树的后序遍历(迭代) 总结首先我们从两个方面讲解二叉树的后序遍历(递归+迭代) 一.二叉树的后序遍历.(递归) 思想: 首先我们从二叉树的根节点开始先遍历其左孩子,①接着同样继续遍历其左孩子的左孩子,直到某个左孩子节点的左孩子为NULL时,②开始遍历其右孩子,如果其为NULL则访问该节点的值域,并返回其双亲节点重复第二步的操作,如果其不为NULL则以该节点为根节点重复第一步的操作.直到访问完所有节点时结束递归. 代码: void BTreePost