java - 我如何在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

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

递归的基本情况是使用 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);
    }
}