当前位置 博文首页 > 龚厂长的博客：二叉树之前序遍历、中序遍历、后续遍历
刷leetcode的时候，看到三道题：145. 二叉树的后序遍历、94. 二叉树的中序遍历、144. 二叉树的前序遍历。正好趁着这三道题，回顾一下二叉树的遍历算法。
前中后遍历是以根的顺序区分的。
下面按照leetcode题目要求给出每个遍历算法的递归和非递归程序。
在这三个题目里面，树节点都是使用TreeNode表示的，代码如下：
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;
}
}
下面的代码假设输入的为下图的树：
144. 二叉树的前序遍历
前序遍历的递归程序。
public class PreorderTraversal {
public static void main(String[] args)throws Exception {
PreorderTraversal code=new PreorderTraversal();
TreeNode right=new TreeNode(2,new TreeNode(3),null);
TreeNode root=new TreeNode(1,null,right);
System.out.println(code.preorderTraversal(root));
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
traverByRecursion(root,res);
return res;
}
//递归遍历
private void traverByRecursion(TreeNode root,List<Integer> list) {
if(root==null){
return ;
}
list.add(root.val);//先遍历根
this.traverByRecursion(root.left,list);//遍历左子树
this.traverByRecursion(root.right,list);//遍历右子树
}
}
前序遍历的非递归程序。
public class PreorderTraversal {
public static void main(String[] args)throws Exception {
PreorderTraversal code=new PreorderTraversal();
TreeNode right=new TreeNode(2,new TreeNode(3),null);
TreeNode root=new TreeNode(1,null,right);
System.out.println(code.preorderTraversal(root));
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
traverByNotRecursion(root,res);
return res;
}
//非递归遍历
private void traverByNotRecursion(TreeNode root,List<Integer> list) {
if(root==null){
return ;
}
//使用stack模拟计算机栈
List<TreeNode> stack=new ArrayList<>();
stack.add(root);
do{
TreeNode node=stack.remove(stack.size()-1);
list.add(node.val);//遍历根
if(node.right!=null){
stack.add(node.right);//添加右子树
}
if(node.left!=null){
stack.add(node.left);//添加左子树
}
}while(stack.size()!=0);
}
}
94. 二叉树的中序遍历
中序遍历的递归程序。
public class InorderTraversal {
public static void main(String[] args)throws Exception {
InorderTraversal code=new InorderTraversal();
TreeNode right=new TreeNode(2,new TreeNode(3),null);
TreeNode root=new TreeNode(1,null,right);
System.out.println(code.inorderTraversal(root));
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
traverByRecursion(root,res);
return res;
}
//递归遍历
private void traverByRecursion(TreeNode root, List<Integer> list) {
if(root==null) {
return;
}
this.traverByRecursion(root.left,list);//遍历左子树
list.add(root.val);//遍历根
this.traverByRecursion(root.right,list);//遍历右子树
}
}
中序遍历的非递归程序。
public class InorderTraversal {
public static void main(String[] args)throws Exception {
InorderTraversal code=new InorderTraversal();
TreeNode right=new TreeNode(2,new TreeNode(3),null);
TreeNode root=new TreeNode(1,null,right);
System.out.println(code.inorderTraversal(root));
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
traverByNotRecursion(root,res);
return res;
}
//非递归遍历
private void traverByNotRecursion(TreeNode root, List<Integer> list) {
if(root==null){
return ;
}
//使用stack模拟计算机栈
List<TreeNode> stack=new ArrayList<>();
while(!stack.isEmpty()||root!=null){
if(root!=null){
stack.add(root);
root=root.left;
}else{
root=stack.remove(stack.size()-1);
list.add(root.val);
root=root.right;
}
}
}
}
145. 二叉树的后序遍历
后序遍历的递归程序。
public class PostorderTraversal {
public static void main(String[] args)throws
