프로그래머 코드 면접 안내서 두 갈래 나무의 서열화와 반서열화 - 자바 실현

두 갈래 나무의 서열화와 반서열화

제목 설명:

두 갈래 나무가 파일로 기록되는 과정을 두 갈래 나무의 서열화라고 하고, 파일 내용을 통해 원래의 두 갈래 나무를 재건하는 과정을 두 갈래 나무의 반서열화라고 한다.두 갈래 나무의 머리 노드 헤드를 정하고 두 갈래 나무의 절점 값의 유형은 32위 정형으로 알려져 있다.두 갈래 트리의 서열화와 반서열화 방안을 설계하고 코드로 실현하십시오.【요구】1, 선행 역행 서열화와 반서열화 실현 2, 층별 역행 서열화와 반서열화 실현

문제 난이도:

medium

제목 사고방식:

1. 먼저 순서대로 정렬화한다. 즉, 귀속적인 방식을 사용하고null을 만나면'#', 반대로''를 연결한다.2. 반서열화, 먼저 문자열 분할을 사용하여 모든 문자열을 대기열에 추가한다.귀속 방식을 채택하여 각각 두결점과 좌우 아이의 노드를 찾다.

코드 구현:

       public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    // 
    public static String serialByPre(Node head) {
        if (head == null) {
            return "#_";
        }
        String res = head.value + "_";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }

    // 
    public static Node reconByPreString(String preStr) {
        String[] vlaue = preStr.split("_");
        Queue<String> queue = new LinkedList<>();
        for (String str : vlaue) {
            queue.offer(str);
        }
        return reconPreOrder(queue);
    }

    private static Node reconPreOrder(Queue<String> queue) {
        String value = queue.poll();
        if (value.equals("#")) {
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.left = reconPreOrder(queue);
        head.right = reconPreOrder(queue);
        return head;
    }


    // 
    public static String serialByLevel(Node head) {
        if (head == null) {
            return "#_";
        }
        String res = head.value + "_";
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            if (head.left != null) {
                queue.offer(head.left);
                res += head.left.value + "_";
            } else {
                res += "#_";
            }
            if (head.right != null) {
                queue.offer(head.right);
                res += head.right.value + "_";
            } else {
                res += "#_";
            }
        }
        return res;
    }

    // 
    public static Node reconByLevelString(String levelStr){
        if (levelStr == null || levelStr.length() == 0){
            return null;
        }
        String[] str = levelStr.split("_");
        int index = 0;
        Queue<Node> queue = new LinkedList<>();
        Node head= generateNodeByString(str[index++]);
        if (head == null){
            return null;
        }
        queue.offer(head);
        Node node = null;
        while (!queue.isEmpty()){
            node = queue.poll();
            node.left = generateNodeByString(str[index++]);
            node.right = generateNodeByString(str[index++]);
            if (node.left!=null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return head;
    }

    private static Node generateNodeByString(String s) {
        if (s.equals("#")){
            return null;
        }
        return new Node(Integer.valueOf(s));
    }