java - 有没有一种简单的方法来比较二叉树的路径？

Question

我需要找到一个按字母顺序最高的单词。

从叶子到根的路径，没有像下面示例中的 XHCA、FHCA、XFA、GFA 那样的侧向跟踪

例子：

INPUT  
      A
     / \
    C   F
   /   / \ 
  H   X   G
 / \
X   F

OUTPUT
XHCA

我找到最高单词的功能：

String find(){
        String wordLeft = "", wordRight = "";
        if(left != null) wordLeft += left.find() + getValue();
        if(right != null) wordRight += right.find() + getValue();

        return left == null && right == null ? String.valueOf(getValue()) : left == null ? wordRight : right == null ? wordLeft : compare(wordLeft, wordRight);
    }
    String compare(String wordLeft, String wordRight){
        if(wordLeft.compareTo(wordRight) > 0) return wordLeft;
        else if(wordLeft.compareTo(wordRight) < 0) return wordRight;
        else return wordLeft.length() > wordRight.length() ? wordLeft : wordRight;
    }

它适用于大多数输入，但是对于一棵更大的树来说输出不正确（对于我来说太大而无法找到错误发生的位置，甚至无法在此处发布它，因为它在 .txt 文件中包含超过 260000 个节点）。我找不到任何具有类似错误的小树。

我的问题：

• 我的算法有任何逻辑问题吗？
• 有没有更简单的方法来解决这个问题？

源代码：

public class Tree{
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new File(args[0]));
        String line;
        Node root = new Node('+'); //Replacement value until we find the proper root
        while(sc.hasNextLine()){
            line = sc.nextLine();
            char[] arr = line.toCharArray();
            if(arr.length > 2){
                root.addNode(arr);
            }else if(arr.length == 1){
                root.setValue(arr[0]);
            }
        }
        System.out.println(root.find());
    }
}

class Node {
    char value;
    Node right, left;
    Node(char value){
        this.value = value;
    }

    void addNode(char[] arr){
        if(arr.length == 3){
            if(arr[2] == 'L') {
                if (left == null) left = new Node('/');
                left.setValue(arr[0]);
            }
            if(arr[2] == 'R') {
                if (right == null) right = new Node('\\');
                right.setValue(arr[0]);
            }
        }else if(arr.length > 3){
            char[] newArr = new char[arr.length - 1];
            newArr[0] = arr[0];
            newArr[1] = arr[1];
            for(int i = 2; i < newArr.length; i++){
                newArr[i] = arr[i + 1];
            }

            if(arr[2] == 'L') {
                if (left == null) left = new Node('/');
                left.addNode(newArr);
            }
            if(arr[2] == 'R') {
                if (right == null) right = new Node('\\');
                right.addNode(newArr);
            }
        }
    }

    String find(){
        String wordLeft = "", wordRight = "";
        if(left != null) wordLeft += left.find() + getValue();
        if(right != null) wordRight += right.find() + getValue();

        return left == null && right == null ? String.valueOf(getValue()) : left == null ? wordRight : right == null ? wordLeft : compare(wordLeft, wordRight);
    }
    String compare(String wordLeft, String wordRight){
        if(wordLeft.compareTo(wordRight) > 0) return wordLeft;
        else if(wordLeft.compareTo(wordRight) < 0) return wordRight;
        else return wordLeft.length() > wordRight.length() ? wordLeft : wordRight;
    }
    char getValue(){
        return this.value;
    }
    void setValue(char value){
        this.value = value;
    }
}

标签： javaalgorithmbinary-tree