二叉树的遍历
实现二叉树先序，中序和后序遍历
http://www.nowcoder.com/questionTerminal/a9fec6c46a684ad5a3abd4e365a9d362
题目链接：
二叉树遍历主要有两种，递归和非递归的遍历，第一种递归式的，比较简单，下面是我代码的模拟：
package AAAA;
import java.util.ArrayList;
/***
* https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=188&tags=&title=&diffculty=0&judgeStatus=0&rp=1
* 二叉树的先序后序中序遍历
*/
public class demo171 {
public static class TreeNode {
int var = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int var) {
this.var = var;
}
}
public static void main(String[] args) {
//threeOrders(0)
//建立一个二叉树
TreeNode root= new TreeNode(1);
TreeNode leftNode= new TreeNode(2);
TreeNode rightNode= new TreeNode(3);
TreeNode leftNode1= new TreeNode(4);
root.left=leftNode;
root.right=rightNode;
leftNode.left=leftNode1;
//遍历出二叉树
int[][] result = threeOrders(root);
System.out.println("先序遍历为："+first);
System.out.println("中序遍历为："+mid);
System.out.println("后序遍历为："+last);
for (int[] ints : result) {
for (int i = 0; i < ints.length; i++) {
System.out.print(ints[i]+" ");
}
System.out.println("");
}
}
private static ArrayList<Integer> first=new ArrayList<>();
private static ArrayList<Integer> mid=new ArrayList<>();
private static ArrayList<Integer> last=new ArrayList<>();
public static int[][] threeOrders (TreeNode root) {
int[][] result=new int[3][];
firstCode(root);
midCode(root);
lastCode(root);
result[0]=toIntArray(first);
result[1]=toIntArray(mid);
result[2]=toIntArray(last);
return result;
}
//先序
private static void firstCode(TreeNode root) {
if (root != null) {
first.add(root.var);
firstCode(root.left);
firstCode(root.right);
}
}
//中序
private static void midCode(TreeNode root) {
if (root != null) {
midCode(root.left);
mid.add(root.var);
midCode(root.right);
}
}
//后续遍历
private static void lastCode(TreeNode root) {
if (root != null) {
lastCode(root.left);
lastCode(root.right);
last.add(root.var);
}
}
//讲ArrayList转换为整型数组
private static final int[] toIntArray(ArrayList<Integer> arrayList){
int[] intArray = arrayList.stream().mapToInt(Integer::intValue).toArray();
return intArray;
}
}
由于递归比较耗时，下面这个是使用栈结构进行辅助的非递归解法，特别注意，为什么要是使用栈的结构，而不直接使用while循环，这里主要有两点：
1，使用栈结构可以对栈进行记录，是否为空，这是单纯的while循环用不到的
2，先进后出的特性
下面这个是我没有借助于栈结构写的代码，相信聪明的你已经发现其中的问题了，展示一下
package AAAA;
import java.util.ArrayList;
import java.util.LinkedList;
public class demo174 {
//自定义树的数据结构
public static class TreeNode {
int var = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int var) {
this.var = var;
}
}
public static void main(String[] args) {
TreeNode root= new TreeNode(1);
TreeNode leftNode= new TreeNode(2);
TreeNode rightNode= new TreeNode(3);
root.left=leftNode;
root.right=rightNode;
pp1(root);
pp2(root);
pp3(root);
System.out.println(first);
System.out.println(mid);
System.out.println(last);
}
private static ArrayList<Integer> first=new ArrayList<>();
private static ArrayList<Integer> mid=new ArrayList<>();
private static ArrayList<Integer> last=new ArrayList<>();
public static int[][] threeOrders (TreeNode root) {
int[][] result=new int[3][];
pp1(root);
pp2(root);
pp3(root);
result[0]=toIntArray(first);
result[1]=toIntArray(mid);
result[2]=toIntArray(last);
return result;
}
private static void pp1(TreeNode root){
if(root!=null){
first.add(root.var);
TreeNode p=root;
while(p.left!=null){
p=p.left;
first.add(p.var);
}
TreeNode q=root;
while(q.right!=null){
q=q.right;
first.add(q.var);
}
}
}
private static void pp2(TreeNode root){
if(root!=null){
TreeNode p=root;
while(p.left!=null){
p=p.left;
mid.add(p.var);
}
mid.add(root.var);
TreeNode q=root;
while(q.right!=null){
q=q.right;
mid.add(q.var);
}
}
}
private static void pp3(TreeNode root){
if(root!=null){
TreeNode p=root;
while(p.left!=null){
p=p.left;
last.add(p.var);
}
TreeNode q=root;
while(q.right!=null){
q=q.right;
last.add(q.var);
}
}
last.add(root.var);
}
private static void pp4(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.pop();
System.out.print(root.var+" ");
if(root.left!=null) {
queue.add(root.left);
}
if(root.right!=null) {
queue.add(root.right);
}
}
}
//讲ArrayList转换为整型数组
private static final int[] toIntArray(ArrayList<Integer> arrayList){
int[] intArray = arrayList.stream().mapToInt(Integer::intValue).toArray();
return intArray;
}
}使用栈解决模拟递归遍历要注意一点，后序遍历需要设计标记值，所以说栈是完全可以替代递归的
package AAAA;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
public class demo173 {
//自定义树的数据结构
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public static void main(String[] args) {
TreeNode root= new TreeNode(1);
TreeNode leftNode= new TreeNode(2);
TreeNode rightNode= new TreeNode(3);
root.left=leftNode;
root.right=rightNode;
pp1(root);
pp2(root);
pp3(root);
System.out.println(first);
System.out.println(mid);
System.out.println(last);
}
private static ArrayList<Integer> first=new ArrayList<>();
private static ArrayList<Integer> mid=new ArrayList<>();
private static ArrayList<Integer> last=new ArrayList<>();
public static int[][] threeOrders (TreeNode root) {
int[][] result=new int[3][];
pp1(root);
pp2(root);
pp3(root);
result[0]=toIntArray(first);
result[1]=toIntArray(mid);
result[2]=toIntArray(last);
return result;
}
private static void pp1(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
while(treeNode!=null || !stack.isEmpty()){
//迭代访问节点的左孩子，并入栈
while(treeNode != null){
first.add(treeNode.val);
stack.push(treeNode);
treeNode = treeNode.left;
}
//如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if(!stack.isEmpty()){
treeNode = stack.pop();
treeNode = treeNode.right;
}
}
}
private static void pp2(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
while(treeNode!=null || !stack.isEmpty()){
while(treeNode != null){
stack.push(treeNode);
treeNode = treeNode.left;
}
if(!stack.isEmpty()){
treeNode = stack.pop();
mid.add(treeNode.val);
treeNode = treeNode.right;
}
}
}
private static void pp3(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
TreeNode lastVisit = null; //标记每次遍历最后一次访问的节点
while(treeNode!=null || !stack.isEmpty()){//节点不为空，结点入栈，并且指向下一个左孩子
while(treeNode!=null){
stack.push(treeNode);
treeNode = treeNode.left;
}
//栈不为空
if(!stack.isEmpty()){
//出栈
treeNode = stack.pop();
if(treeNode.right == null || treeNode.right == lastVisit) {
last.add(treeNode.val);
lastVisit = treeNode;
treeNode = null;
}else{
stack.push(treeNode);
treeNode = treeNode.right;
}
}
}
}
private static void pp4(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.pop();
System.out.print(root.val+" ");
if(root.left!=null) {
queue.add(root.left);
}
if(root.right!=null) {
queue.add(root.right);
}
}
}
//讲ArrayList转换为整型数组
private static final int[] toIntArray(ArrayList<Integer> arrayList){
int[] intArray = arrayList.stream().mapToInt(Integer::intValue).toArray();
return intArray;
}
}
蚂蚁集团公司福利 103人发布