二叉树的遍历

实现二叉树先序，中序和后序遍历

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，先进后出的特性
下面这个是我没有借助于栈结构写的代码，相信聪明的你已经发现其中的问题了，展示一下

二叉树的遍历

全站热榜

创作者周榜