找到二叉树从根到叶的所有路径

Question

我写了一个递归算法来找到二叉树的所有路径。基本上，您会找到最左边的路径，将节点放入堆栈中并逐渐找到正确的分支。据我测试，该算法运行良好，但在递归期间添加了一个空条目。

例如，下面提供了一个示例树，

代码应提供路径：

[4, 5, 4, 5]
[4, 5, 4, 12, 13]
[4, 6, 1]
[4, 6, 6]

节点定义在这里，

private static class Node {

        public int key;

        public Node left;
        public Node right;

        public Node(int key) {
            this.key = key;
        }
    }

下面提供的查找所有路径的算法，

/*
 * find all the paths of a binary search tree
 * */
private static void findPaths(Node node, List<List<Integer>> lists, Stack<Node> stack) {

    if (node == null) {
        return;
    }

    List<Integer> list = null;

    stack.push(node);

    while (node.left != null) {
        node = node.left;
        stack.push(node);
    }

    /////////
    if (stack.peek().right != null) {
        findPaths(stack.peek().right, lists, stack);
    }
    /////////


    if (stack.size() > 0) {
        list = new ArrayList<>();
    }

    for (Node n : stack) {
        list.add(n.key);
    }

    lists.add(list);

    Node right = null;

    /*
     * i.    pop till the stack has elements
     * ii.   delete the old left paths that are already included
     * iii.  delete the old right path that are already included
     *
     * */
    while (stack.size() >0 && (stack.peek().right == null || stack.peek().right.equals(right))) {
        right = stack.pop();
    }


    /*
     * for the right paths
     * */
    if (stack.size() == 0) {
        return;
    }

    right = stack.peek().right;

    findPaths(right, lists, stack);
}

我调试了这个问题，发现当我到达计算结束时，

       if (stack.size() == 0) {
            return;
        }

代码命中 return 然后没有结束该方法的所有工作，它仍然在里面播放并转到这里，

if (stack.size() > 0) {
        list = new ArrayList<>();
    }

    for (Node n : stack) {
        list.add(n.key);
    }

    lists.add(list);

很明显，后来做不了什么，最后离开了这个方法。

如果有人能帮助我改进代码，我将不胜感激。我假设它来自使用 2 return 语句。在 Java 中是否允许，如果允许，该情况的演练是什么？

Answer 1

如评论中所述，您不需要单独的堆栈。您可以使用递归调用和来自子节点的 return 路径，并将父节点添加到每个可用路径。

private static List<List<Integer>> findPaths(Node node){

    if (node == null) 
        return new ArrayList<List<Integer>>();

    List<List<Integer>> paths = new ArrayList<List<Integer>>();

    List<List<Integer>> left_subtree = findPaths(node.left);
    List<List<Integer>> right_subtree = findPaths(node.right);


    for(int i=0;i<left_subtree.size();++i){
        List<Integer> new_path = new ArrayList<Integer>();
        new_path.add(node.key);
        new_path.addAll(left_subtree.get(i));
        paths.add(new_path);
    }

    for(int i=0;i<right_subtree.size();++i){
        List<Integer> new_path = new ArrayList<Integer>();
        new_path.add(node.key);
        new_path.addAll(right_subtree.get(i));
        paths.add(new_path);
    }


    if(paths.size() == 0){
        paths.add(new ArrayList<Integer>());
        paths.get(0).add(node.key);
    }

    return paths;
}

Answer 2

嗯，C++ 在此类代码方面与 Java 没有什么不同。下面是上述问题的 C++ 实现。

vector< vector< int > > ans;

void solution(TreeNode *root, vector<int> &current){
    if(root == NULL)
        return;
    current.push_back(root->val);
    if(root->left == NULL and root->right == NULL)
        ans.push_back(current);

    if(root->left)
        solution(root->left, current);

    if(root->right)
        solution(root->right, current);

    current.pop_back();
} 


vector<vector<int> > Solution::pathSum(TreeNode* A) {
    ans.clear();
    vector<int> current;
    solution(A, current);
    return ans;
}

上述方法使用递归并维护路径。每当我们找到解决方案，即叶子，我们认为这是一个解决方案并弹出该元素以搜索沿着树向下移动的其他解决方案。

Answer 3

我有一个递归解决方案，可以提供从二叉树的根到叶的所有路径。下面提供了解决方案，

public static List<List<Node>> findAllPaths(List<List<Node>> paths, Node node, List<Node> path) {

        if (node == null) {
            return paths;
        }

        path.add(node);

        if (node.left == null && node.right == null) {

            paths.add(path);
            return paths;
        }

        //
        else {
            findAllPaths(paths, node.left, new ArrayList<>(path));
            findAllPaths(paths, node.right, new ArrayList<>(path));
        }

        return paths;
    }

找到二叉树从根到叶的所有路径

find all paths from root to leaf of a binary tree

java

algorithm

tree

binary-tree