通过“FBI树”复习二叉树算法（洛谷P1087题题解，Java语言描述）

题目要求

P1087题目链接

分析

所谓的“FBI树”，其实就是一种二叉树，最后的结果也无非就是二叉树的后序遍历序列。

所以，考察的知识点就是——二叉树基本算法的灵活运用。

本题关键在于如何建树，这个要求需要我们好好读题。 建树的时候需要先识别当前结点分到的String的类型，然后把String二分分别交给左右儿子，标准的递归过程。

String的类型，根据题目的描述已经很明确了： 全1：I 全0：B 有0有1：F

这个"F"、“B”、“I” 其实就是结点的value，最后在遍历的时候打印出来就行。

生成结点的代码：

return sequence.contains("0") ? (sequence.contains("1") ? new Node("F") : new Node("B")) : new Node("I");

建树的代码：

private static void produceTree(String sequence, Node node) {
    if (sequence.length() == 1) {
        return;
    }
    String leftPart = sequence.substring(0, sequence.length()/2);
    node.left = produceNode(leftPart);
    produceTree(leftPart, node.left);
    String rightPart = sequence.substring(sequence.length()/2);
    node.right = produceNode(rightPart);
    produceTree(rightPart, node.right);
}

后序遍历递归的代码：

private void postOrder(Node node) {
    if (node == null) {
        return;
    }
    if (node.left != null) {
        postOrder(node.left);
    }
    if (node.right != null) {
        postOrder(node.right);
    }
    result.append(node.value);
}

AC代码（Java语言描述）

import java.util.Scanner;

public class Main {

    private static StringBuilder result = new StringBuilder();

    private static class Node {
        T value;
        Node left;
        Node right;
        Node(T value) {
            this.value = value;
        }
    }

    private static class FBITree {
        Node root;
        private void postOrder(Node node) {
            if (node == null) {
                return;
            }
            if (node.left != null) {
                postOrder(node.left);
            }
            if (node.right != null) {
                postOrder(node.right);
            }
            result.append(node.value);
        }
    }

    private static Node produceNode(String sequence) {
        return sequence.contains("0") ? (sequence.contains("1") ? new Node("F") : new Node("B")) :
                new Node("I");
    }

    private static void produceTree(String sequence, Node node) {
        if (sequence.length() == 1) {
            return;
        }
        String leftPart = sequence.substring(0, sequence.length()/2);
        node.left = produceNode(leftPart);
        produceTree(leftPart, node.left);
        String rightPart = sequence.substring(sequence.length()/2);
        node.right = produceNode(rightPart);
        produceTree(rightPart, node.right);
    }

    public static void main(String[] args) {
        FBITree tree = new FBITree();
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        String sequence = scanner.next();
        scanner.close();
        tree.root = produceNode(sequence);
        produceTree(sequence, tree.root);
        tree.postOrder(tree.root);
        System.out.println(result);
    }

}

回顾二叉树基本算法

《二叉树基本算法锦集（Java语言描述）》