欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-15 10:45:44
目录一、前序遍历1.题目描述2.输入输出示例3.解题思路4.代码实现二、中序遍历1.题目描述2.输入输出示例3.解题思路4.代码实现三、后序遍历1.题目描述2.输入输出示例3.解题思路4.代码实现一、...

一、前序遍历

1.题目描述

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

2.输入输出示例

示例 1:

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

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

输出:[1,2,3]

示例2:

输入:root = []

输出:[]

示例 3:

输入:root = [1]

输出:[1]

3.解题思路

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

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

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:

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

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

输出:[1,3,2]

示例 2:

输入:root = []

输出:[]

示例 3:

输入:root = [1]

输出:[1]

3.解题思路

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

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

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.解题思路

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

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

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 数据结构的资料请关注其它相关文章!