树的遍历

创建案例

public static void main(String[] args) {
    // 根节点为 1
    // 左子节点为 2，右子节点为 3     2 的左子节点为 4，右子节点为 5
    // 3 的左子节点为 6，右子节点为 7    4 的左子节点为 8，右子节点为 9     5 的左子节点为 10
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2, new TreeNode(4, new TreeNode(8), new TreeNode(9)), new TreeNode(5, new TreeNode(10), null));
    root.right = new TreeNode(3, new TreeNode(6), new TreeNode(7));
    pre(root);
    System.out.println();
    mid(root);
    System.out.println();
    after(root);
    System.out.println();
    tier(root);
}
    public static 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;
        }
    }

层序遍历

public static void tier(TreeNode root) {
    //利用栈进行每层节点的排列
    Stack<TreeNode> stack = new Stack<>();
    Stack<TreeNode> temp = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            System.out.print(pop.val+" ");
            if (pop.left != null) temp.push(pop.left);
            if (pop.right != null) temp.push(pop.right);
        }
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }
}

前序遍历

    public static void pre(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val+" ");
        if (root.left != null) pre(root.left);
        if (root.right != null) pre(root.right);
    }

中序遍历

public static void mid(TreeNode root) {
    if (root == null) return;
    if (root.left != null) mid(root.left);
    System.out.print(root.val+" ");
    if (root.right != null) mid(root.right);
}

后序遍历

public static void after(TreeNode root) {
    if (root == null) return;
    if (root.left != null) after(root.left);
    if (root.right != null) after(root.right);
    System.out.print(root.val+" ");
}