用任意合法序列建立一棵二叉树（洛谷P1305题题解，Java语言描述）

前言

这题是极其麻烦极其麻烦的一道题（前提是你不知道它有套路）…… 我们不讲那些歪门邪道，我们正儿八经的解一下，想正经求解，很麻烦很麻烦。。。

题目要求

P1305题题解

分析

这题你看着容易，那是你想当然认为建立一棵树，给你的序列就是先根的，其实真实情况里不一定是……（当然本题是，所以是橙题……）

这题肝的我简直要暴毙，要多麻烦有多麻烦，大家如果有改进策略请告诉我，我会虚心接受了。。。写这么长代码累死人啦！！

我讲讲我分析的思路吧：

我们要自己编写结点类，其实结点凑起来就是tree，我们控一下root就可以咯。 手写Node，由于指定类型，所以不加泛型，不加setter、getter，玩最简单的版本：

    static class Node {
        char data;
        Node left, right;
        Node(char data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return data == node.data;
        }
        @Override
        public int hashCode() {
            return Objects.hash(data);
        }
    }

对咯，这个必须是（静态）内部类，因为luoguOJ不识别，你写成另一个class会判CE的。。。。。。静态的内部类是OK的，因为静态不能访问非静态的，这会给方法里的调用带来麻烦。 还有就是一定要重写hashCode()和equals()，我们可是需要用data来区别Node的呀！！

首先我们建立一棵树，需要建立临时根结点，由于我们想知道这个结点是否已经在树里面，我们不想再次遍历，那我们可以建立一个HashMap，存储已经加入树中的结点。 我们还需要一个HashMap，用来为未插入树中的结点提供查找的便利。

将初始化的根结点保存为根结点，左右儿子加上去。不过这个题无论何时都要注意 ‘*’ 的存在，必须不能插入data为 ‘*’ 的结点。

接下来开循环，每次读一行数据，然后切成三份(toCharArray())，用三个char存储。 循环里面先看看这个临时的根结点是不是在map里，如果有就说明它在树里，它不可能还有左右儿子，所以肯定是原先作为某个子结点的，进行一下替换。 如果不在map里，就去unAddedMap里找，这里有的话思路同上，只不过这是一群没加入树里的临时树，相当于与真正的树构成了一个森林而已…… 如果都不在，那好，这就是没有出现过的结点，我们看看它是不是新的根结点，这个判断要用临时根结点的左右儿子分别与当前真实根节点比较，如果equals就换根，注意换根以后要查右儿子在不在unAddedMap里（肯定不在map里）。。如果不是换根的情况那就只能把它塞进unAddedMap里了，毕竟这在当前是一棵 “孤儿树”，无依无靠呜呜呜~~

大致是这样，具体的看我代码注释吧，能看完说明你是个狠人，哦不，狼人（比狠人还狠一、）。。。

哦哦哦，差点忘说了，这个算法有一部分的逻辑是这样的： 毕竟我们这个森林是需要合并的，当合并的时候呢，就要把unAddedMap里的那个结点换掉临时结点（未来的老祖宗——新根）的某个儿子（我WA的那次就是因为这个原因，太难了），然后在unAddedMap里递归删除，在map里递归插入。。。。

这需要两个static的辅助方法（private即可），很nice！！！

递归删除：

    private static void deleteRecursively(Node root, Map unAddedMap) {
        if (root == null) {
            return;
        }
        unAddedMap.remove(root.data);
        deleteRecursively(root.left, unAddedMap);
        deleteRecursively(root.right, unAddedMap);
    }

递归插入：

    private static void addRecursively(Node root, Map map) {
        if (root == null) {
            return;
        }
        map.put(root.data, root);
        addRecursively(root.left, map);
        addRecursively(root.right, map);
    }

最后的结果也需要递归先序遍历：

    private static void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.data);
        preOrder(root.left);
        preOrder(root.right);
    }

第一次提交——CE

这次CE就是因为没把Node类作为内部类，不能被OJ识别所以判错。。。。

第二次提交——WA

这个WA就是因为没换，具体原因我忘了诶，代码奉上，可以自己发掘其“魅力”（毫无魅力的破代码） 这是错的哈，正解在下面。。。

import java.util.*;

public class Main {

    static class Node {
        char data;
        Node left, right;
        Node(char data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return data == node.data;
        }
        @Override
        public int hashCode() {
            return Objects.hash(data);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = Integer.parseInt(scanner.nextLine());
        if (num == 0) {
            return;
        }
        //树非空，进行一系列初始化
        Map map = new HashMap(num);
        Map unAddedMap = new HashMap(num);
        char[] firstChars = scanner.nextLine().toCharArray();
        //初始化根结点
        Node root = new Node(firstChars[0]);
        map.put(firstChars[0], root);
        if (firstChars[1] != '*') {
            root.left = new Node(firstChars[1]);
            map.put(firstChars[1], root.left);
        }
        if (firstChars[2] != '*') {
            root.right = new Node(firstChars[2]);
            map.put(firstChars[2], root.right);
        }
        //循环num-1次
        for (int i = 1; i