java - 找到树中从叶子到根的路径

Question

我看到了很多关于树以及如何递归搜索它们的例子，但不像我的例子。所以我决定问问。

如何找到从任意叶子到根的路径？

我的问题是每个父节点有很多子节点。这是我的代码示例:

 private LinkedList<TreeNode> findPath(LinkedList<TreeNode> path, TreeNode root, TreeNode leaf){
    if(root == null || root.name==null) return null;

    path.add(root);

    if(root.name.equals(leaf.name))
        return path;

    //Check if the leaf that we are looking for is one of the root children
    if(root.children==null) return null;
    for(TreeNode children : root.children){
        if(children.name.equals(leaf.name)){
            path.add(children);
            return path;
        }
    }
    //Search in all the childrens of the root recursively
    for(TreeNode children : root.children){
        LinkedList<TreeNode> result =  findPath(path, children, leaf);
        if(result != null)
            return result;
    }

    //The leaf is not found. 
    return null;
}

问题是，每次我检查一个子节点时，如果我在那里找不到我的叶子，我就会收回，但我已经在路径中添加了子节点，并且我的路径变得非常大。

Answer 1

此实现假设每个树节点“知道”其父节点:

private List<TreeNode> findPath(TreeNode root, TreeNode leaf) {
    List<TreeNode> path = new ArrayList<>();
    TreeNode node = leaf;
    do {
        path.add(node);
        node = node.getParent();
    } while (node != root);

    return path;
}

当然，您应该为根和叶添加有效性检查，并考虑如果节点(直接或间接)是其自己的父节点，则可能出现无限循环。

如果您的树节点仅包含其子节点，但子节点不“知道”其父节点(如果您拥有树节点的代码，您可能应该更改父节点)，则它会变得更加复杂，因为树必须是递归搜索:

public static List<TreeNode> findPath(TreeNode root, TreeNode leaf) {
    LinkedList<TreeNode> path = new LinkedList<>();
    findPathHelper(root, leaf, path);
    return path;
}

private static boolean findPathHelper(TreeNode root, TreeNode leaf, List<TreeNode> path) {
    if (root == leaf) {
        path.add(root);
        return true;
    }

    for (TreeNode treeNode : root.children) {
        if (findPathHelper(treeNode, leaf, path)) {
            path.add(root);
            return true;
        }
    }
    return false;
}