java - 我如何在Java中找到树中最长的单词(没有循环(for,while,do ...))
问题描述
如何在没有循环的情况下找到树中最长的单词(for、while、do ...)?
方法头是:
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);
}
}
推荐阅读
- bind - 如何在 @Body 中使用 @bind-PropertyName
- mysql - SQL 查询在 shell 脚本中不起作用
- linux - 无法在监视器中启动脚本
- java - 在java中打印整数的语法是什么
- javascript - 将 post 请求转换为 JSON 文件
- javascript - 控制台日志中的Javascript过滤器数组按升序排列
- php - .htaccess 从带有数字参数的 URL 重定向到带有文本参数的 URL
- python - 在 Python 中查找和连接具有多个列名的数据框
- php - 究竟是什么导致了这个 PHP 代码中的错误?
- java - 为什么我们不能使用 (==) 而不是 .equals() 方法来比较字符串对象?