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

Question

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

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

               4
              /  \
             5    6
            /    / \
           4    1   6
          / \
         5  12
             \
             13

代码应该提供路径:

[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

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

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