我怎样才能在 Java 中找到树中最长的单词（没有循环（for，while，do ...））

Question

如何在没有循环的情况下找到树中最长的单词（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;

但这没有意义。

Answer 1

看起来你只是递归到右子树，但不要忘记左子树。

递归的基本情况是使用空根调用函数时，在这种情况下 return 为空。否则，从根的左右子树中获取最长的字符串（它们可能为空，因此我们需要合并）和 return 这两个字符串中最长的字符串以及根的字符串。

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

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 class ，因此将其视为概念证明）：

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 中找到树中最长的单词（没有循环（for，while，do ...））

How can i find the longest word in a tree in Java (without a loop (for, while, do ...))

java

recursion

binary-tree