栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指offer每日10题Day3

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指offer每日10题Day3

事实证明不能十题的

  • 树前中后序列 递归非递归+层序遍历+按层输出
package offer;

import java.util.*;

//树节点定义
class Node {
    public String value;
    public Node right;
    public Node left;

    public Node(String value) {
        this.value = value;
    }
}

public class Test6 {
    //先序 递归
    public static void preOrder(Node root) {
        if (root == null)
            return;
        System.out.print(root.value);
        preOrder(root.left);
        preOrder(root.right);

    }

    //用栈的形式把递归转写
    public static void preOrder2(Node root) {
        //如果为空就返回
        if (root == null) return;
        //命名一个节点
        Stack stack = new Stack<>();
        //把根节点放进来
        stack.push(root);
        //访问站点是否为空
        //先进后出 所以先右边后左边
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.value);
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }
    }

    //中序
    public static void midOrder(Node root) {
        if (root == null)
            return;
        midOrder(root.left);
        System.out.print(root.value);
        midOrder(root.right);

    }

    //非递归中序 找最左节点
    public static void midOrder2(Node root) {
        //如果为空就返回
        if (root == null) return;
        //命名一个节点
        Stack stack = new Stack<>();
        //找到最左节点
        Node cur = root;
        //一直向左走
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            Node node = stack.pop();
            System.out.print(node.value);
            if (node.right != null)
                cur = node.right;
        }
    }

    //后序
    public static void postOrder(Node root) {
        if (root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value);
    }

    //非递归实现后序遍历
    //先序 根左右 根右左逆序
    //后续 左右根
    public static void postOrder2(Node root) {
        if (root == null)
            return;
        Stack stack = new Stack<>();
        //更改后逆序
        Stack stack2 = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            stack2.push(node);
            if (node.left != null)
                stack.push(node.left);
            if (node.right != null)
                stack.push(node.right);
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().value);
        }
    }

    //层序遍历
    //队里的格式一层层读
    private static void bfs(Node root) {
        if (root == null)
            return;
        Queue queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //打印
            Node node = queue.poll();
            //访问左右孩子
            System.out.println(node.value);
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
    }

    //一层层输出层序遍历  记录queue每一层的大小
    //队里的格式一层层读
    private static List> bfs2(Node root) {
        List> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List res1 = new ArrayList<>();
            while (size-- > 0) {
                //打印
                Node tmp = queue.poll();
                res1.add(tmp.value);
                //访问左右孩子
                if (tmp.left != null)
                    queue.add(tmp.left);
                if (tmp.right != null)
                    queue.add(tmp.right);
            }
            res.add(res1);
        }
        return res;
    }

    public static void main(String[] args) {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");
        Node nodeD = new Node("D");
        Node nodeE = new Node("E");
        Node nodeF = new Node("F");
        Node nodeG = new Node("G");

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.right = nodeF;
        nodeE.left = nodeG;
//        preOrder(nodeA);
//        preOrder2(nodeA);
//        midOrder2(nodeA);
//        postOrder(nodeA);
//        postOrder2(nodeA);
        System.out.println(bfs2(nodeA));

    }
}

两个栈实现队列

package offer;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

//两个栈实现队列先进先出
class Queue {
    private Stack stackA = new Stack<>();
    private Stack stackB = new Stack<>();

    public void push(int element) {
        stackA.push(element);
    }

    //出队操作
    public Integer pop() {
        //如果stackB空 A不为空
        while (stackB.isEmpty()) {
            while (!stackA.isEmpty()) {
                //把A中弹出的放到B里面
                stackB.push(stackA.pop());
            }
        }
        //如果两个都是空的
        if (stackB.isEmpty())
            return -1;
        else return stackB.pop();
    }

}

public class Test7 {
    public static void main(String[] args) {
        Queue q1 = new Queue();
        q1.push(1);
        q1.push(2);
        q1.push(3);
        System.out.println(q1.pop());
        System.out.println(q1.pop());
        System.out.println(q1.pop());
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/953314.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号