java - 如何在Java中的树中找到最长的单词(无循环(用于...，同时做……))

如何在没有循环的情况下找到树上最长的单词（例如，执行...）？

方法头是：

public static String longest(Node tree) {
    return "";
}

在main中是：

System.out.println(longest(tree)); // => tasty

树是：f[o[C[tasty,null],F],E[null,e]] : (Pattern: %value[%left,%right])

我的第一个想法是：

String s = tree.value;
String l = tree.left.value;
String r = tree.right.value;
return s < l || s < r ? longest(tree.right) : s;

但这没有意义。

最佳答案

看来您只是递归到合适的孩子，但不要忘记左边的子树。

递归的基本情况是使用空根调用该函数时，在这种情况下返回null。否则，从根的左侧和右侧子树中获取最长的字符串（这些字符串可能为null，因此我们需要合并），然后将这两个字符串中的最长的字符串与根的字符串一起返回。

这是一个最小的完整示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Main {
    public static String longest(TreeNode tree) {
        if (tree == null) return null;

        var strs = new ArrayList<String>();
        strs.add(longest(tree.left));
        strs.add(longest(tree.right));
        strs.add((String)tree.value);
        return Collections.max(strs,
            Comparator.comparing(s -> s == null ? 0 : s.length()));
    }

    public static void main(String[] args) {
        /*
             a
           /   \
         aaaa   aa
         /       \
        aaa    aaaaa

        */
        var tree = new TreeNode<String>(
            "a",
            new TreeNode<String>(
                "aaaa",
                new TreeNode<String>("aaa", null, null),
                null
            ),
            new TreeNode<String>(
                "aa",
                null,
                new TreeNode<String>("aaaaa", null, null)
            )
        );
        System.out.println(longest(tree)); // => "aaaaa"
    }
}

class TreeNode<T> {
    public T value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(T value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

您还可以将树的节点展平到一个列表中，然后从中选择最长的字符串（TreeNode应该有一个自定义比较器，并且这些方法应该属于Tree类，因此请考虑一下这是概念证明）：

public static String longest(TreeNode tree) {
    var flattened = new ArrayList<String>();
    flatten(tree, flattened);
    return Collections.max(flattened, Comparator.comparing(e -> e.length()));
}

public static void flatten(TreeNode tree, ArrayList<String> result) {
    if (tree != null) {
        flatten(tree.left, result);
        result.add((String)tree.value);
        flatten(tree.right, result);
    }
}

关于java - 如何在Java中的树中找到最长的单词(无循环(用于...，同时做……))，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59336654/