Найти все пути от корня до листа двоичного дерева

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

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