如何在没有循环的情况下找到树上最长的词（例如，这样做……）？
方法头是：
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);
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句