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

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]

输出：[1]

3.解题思路

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

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

2.创建一个栈用来保存右子树

3.先将根结点入栈，避免多次判断栈为空

4.取出栈顶元素（第一次为根结点），从上往下遍历最左侧路径中的每个结点

5.在遍历时判断当前结点的右子树是否为空，非空则入栈

6.遍历结束后，此时栈顶元素为前一个结点的右子树，将栈顶元素取出，将其看作一棵树，继续重复上述操作，即形成循环。

4.代码实现

class Solution {

public List preorderTraversal(TreeNode root) {

List list=new ArrayList<>();

if(root==null){

return list;

}

//创建一个栈用来保存右子树

Stack 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.从上往http://下遍历最左侧路径中的每个结点，并将其保存到栈中，走到cur==null的位置

4.此时栈顶元素为最左侧路径的最后一个结点，将其加入到list并将栈顶元素移除

5.判断最后一个结点的右子树是否为空，过程和上述的过程是一样的，直接将其右子树看作一棵树，整个过程便循环起来

4.代码实现

class Solution {

public List inorderTraversal(TreeNode root) {

List list=new ArrayList<>();

if(root==null){

return list;

}

Stack 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，同时将栈顶元素删除

如果不为空则将右子树看作一棵树，重新进入循环判断

注意：如果按照这样，到了最后的右子树就会一直LTdgUF循环出不来

解决方案：

创建一个prev用来标记已经遍历过的结点，将能否编历的条件改为：top的右子树为空||top的右子树已经遍历过

4.代码实现

class Solution {

public List postorderTraversal(TreeNode root) {

List list=new ArrayList<>();

if(root==null){

return list;

}

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。