如何从文本文件解析节点路径构建二叉树并输出字典序最大字符串

需要从TXT文件构建二叉树，文件每一行描述一个节点，格式为X Y：X是char类型的节点值，Y是描述节点位置的方向字符串。例如C RRL表示节点值为'C'，位置是从根节点出发依次向右(R)、向右(R)、向左(L)。
输出要求为所有从根到叶子的路径拼接成的字符串中字典序最大的那个。程序不能使用Collections或其它Java现成解决方案（比如streams等），同时平均时间复杂度需为O(nlogn)，内存复杂度为O(n)。

示例 #

输入 #

G RR
A
C L
F LLR
X LLL
F R
X RL
H LL

输出 #

XHCA

现有问题 #

目前编写的代码仅能按从根到子的顺序添加节点，若路径上的中间父节点不存在则无法正确创建后续节点，仅树的起始部分结构正确，现有代码如下：

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        File file = new File("fileInput.txt");
        BinaryTree bt = new BinaryTree();
        try(BufferedReader br = new BufferedReader(new FileReader(file))){
            String line;
            while ((line = br.readLine()) != null){
                if(line.length()==1) {
                    bt.direction = "";
                }
                else
                    bt.direction = line.substring(2);
                bt.add(line.charAt(0));
            }
        }
    }

    static class BinaryTree {
        Node root;
        String direction;

        public void add(char letter){
            if(direction.isBlank())
                root = new Node(letter);
            else
                root = addRecursive(root, letter, 0);
        }
        private Node addRecursive(Node current, char letter, int j) {
            if (current == null) {
                    return new Node(letter);
                }
            if(j < direction.length()){
                if(direction.charAt(j)=='L'){
                        current.left = addRecursive(current.left, letter, ++j);
                    }
                else if (direction.charAt(j)=='R') {
                        current.right = addRecursive(current.right, letter, ++j);
                    }
                }
            return current;
        }

        }
    }

    static class Node {
        char letter;
        Node left;
        Node right;

        Node(char letter) {
            this.letter = letter;
            left = null;
            right = null;
        }
    }
}

修复方案 #

1. 解决中间节点缺失问题 #

原有递归逻辑遇到空节点直接返回待插入的目标节点，会把中间路径的节点错误赋值为当前插入值。需要在遍历路径时遇到不存在的中间节点先创建占位节点，走到路径末尾再替换为目标节点值：
修改addRecursive方法如下：

private Node addRecursive(Node current, char letter, int j) {
    // 中间节点不存在，先创建占位节点，用'\0'标识未赋值
    if (current == null) {
        current = new Node('\0');
    }
    // 走到路径最后一位，替换为目标节点值
    if(j == direction.length()){
        current.letter = letter;
        return current;
    }
    if(direction.charAt(j)=='L'){
        current.left = addRecursive(current.left, letter, j+1);
    } else if (direction.charAt(j)=='R') {
        current.right = addRecursive(current.right, letter, j+1);
    }
    return current;
}

2. 实现字典序最大路径查找 #

用深度优先遍历记录当前路径，遇到叶子节点时对比当前路径和已记录的最大路径，保留字典序更大的结果：

• 在BinaryTree类中新增成员变量存储最大路径：String maxPath = "";
• 新增路径查找方法：

public void findMaxPath(Node node, String currentPath) {
    if (node == null) {
        return;
    }
    currentPath += node.letter;
    // 到达叶子节点，对比更新最大路径
    if (node.left == null && node.right == null) {
        if (currentPath.compareTo(maxPath) > 0) {
            maxPath = currentPath;
        }
        return;
    }
    findMaxPath(node.right, currentPath);
    findMaxPath(node.left, currentPath);
}

3. 调整主逻辑 #

读取完全部节点后调用查找方法输出结果，在main方法的try块结束后添加：

bt.findMaxPath(bt.root, "");
System.out.println(bt.maxPath);

复杂度说明 #

• 插入n个节点，每个节点的路径长度平均为O(logn)，插入总耗时O(nlogn)
• 遍历所有节点查找最大路径耗时O(n)，整体平均时间复杂度符合要求
• 内存占用为n个节点+最大路径存储，符合O(n)要求

内容的提问来源于stack exchange，提问作者Pumpkinador