1

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

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

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

 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;
}

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

4

1 回答 1

2

这个实现假设每个树节点都“知道”它的父节点：

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;
}
于 2013-11-07T12:55:34.937 回答