如何进行Java 数据结构中二叉树前中后序遍历非递归的具体实现

本文向您展示了如何在Java数据结构中实现二叉树的非递归遍历。内容简洁易懂，一定会让你大放异彩。希望通过这篇文章的详细介绍，你能有所收获。

00-101

一、前序遍历

给出了二叉树的根节点，并返回其节点值的前序遍历。

00-1010示例1:

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

输出：[1，2，3]

例2:

输入：root=[]

输出：[]

例3:

输入：root=[1]

输出：[1]

00-1010前序遍历：根节点-左子树-右子树

1.判断额外的情况，如果树是空的，直接返回。

2.创建一个堆栈来存储右子树。

3.先把根节点放入栈中，避免多次判断栈为空。

4.取出堆栈的顶部元素(第一次是根节点)，从上到下遍历最左边路径中的每个节点。

5.遍历时，判断当前节点的右子树是否为空；如果不是，它将被放入堆栈。

6.遍历后，此时栈顶元素是上一个节点的右子树，取出栈顶元素，当作树，继续重复上述操作，即形成循环。

1.题目描述

类别解决方案{

publicatlistingerpreordertraverse(treenoderroot){ 0

listinterlist=new ArrayList()；

if(root==null){ 0

returnlist

}

//创建一个堆栈来存储右子树。

StackTreeNodes=newStack()；

TreeNodecur=root

s . push(root)；

//从上到下遍历最左边路径中的每个节点，并保存其右子树堆栈

while(！s.empty()||cur！=null){ 0

cur=s . pop()；

while(cur！=null){ 0

list . add(cur . val)；

如果(正确！=null){ 0

（=NationalBureauofStandards）国家标准局

p;        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 数据结构中二叉树前中后序遍历非递归的具体实现，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注行业资讯频道。