Поиск быстрого алгоритма для нахождения расстояния между двумя узлами в двоичном дереве

Ответ 1

• рассчитать список предков для каждого node
• найти общий префикс
• Последний элемент из общего префикса является самым низким общим предком
• удалить общий префикс из обоих списков предков
• расстояние - это сумма длин остальных списков +1

Ответ 2

Поиск общего предка - почти наверняка более простая задача. Это довольно простой: начните с корня дерева и опустите дерево до тех пор, пока не достигнете node, где вам нужно будет спуститься к разным детям, чтобы добраться до этих двух узлов. Этот node является общим родителем (предполагается, что дерево содержит оба узла, конечно).

Ответ 3

Как все здесь, кажется, знают, что если вы сохраните примечание о расстоянии, каждое из node принадлежит корню, то, как только вы найдете наименьшего общего предка из двух узлов, вы можете определить расстояние, которое они от каждого другие в постоянное время.

Если вы выполняете однократную работу только линейно по размеру дерева, оказывается, что вы можете найти наименьшего общего предка любых двух узлов в постоянное время (независимо от глубины дерева). См. http://en.wikipedia.org/wiki/Lowest_common_ancestor

Алгоритм Баруха Шибера и Узи Вишкина для низшего общего предка вполне практичен для использования и программирования.

Ответ 4

Сделайте два набора, состоящих из предков каждого из них: в то время как объединение наборов пуст, добавьте следующего предка каждого node в соответствующий список. Когда есть общий node, общий предк.

Ответ 5

Во-первых, найдите высоту первого элемента. Кроме того, верните путь, чтобы попасть туда, используя связанный список. Вы можете сделать это в O (logN). Предположим, что дерево сбалансировано, где высота - logN. пусть H1 = высота первого элемента.

Тогда, найдите высоту во втором элементе. Кроме того, верните путь, чтобы попасть туда, используя связанный список. Вы можете сделать это в O (logN). Пусть H2 = высота второго элемента.

Проследите все связанные связанные списки, пока значения не станут равными (пути расходятся) Перед тем, как они расходятся, назовите высоту этого node H3.

Таким образом, самый длинный путь H1 + H2 - 2 * H3 (так как вам нужно, чтобы H1 перешел на H1 и H2, чтобы перейти на H2.Но на самом деле, вы можете проследить назад от H1 до H1-H3. а затем переместиться в H2 из H3. Таким образом, это (H1-H3) + (H2-H3) = H1 + H2 -2 * H3.

Детали реализации должны быть прямолинейными.

search(Tree* Head, Node* Value, LinkedList path, int distance); 

Таким образом,

search(Head, Value1, path1, height1); 
search(Head, Value2, path2, height2); 

i = 0; 
while (path1[i] == path2[i])
{
    i++; 
}
height3 = i-1; 
return height1+height2- 2*height3; 

Сложность времени: O (logN) + O (logN) + O (logN) = O (logN) Космическая сложность: O (logN) (для хранения связанного списка расстояний)

Ответ 6

здесь реализована реализация DP для расстояния BT. Не оптимальный, но интересный. он создает дерево 1-го, с входным массивом.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by juanmf on 05/02/17.
 */
public class Main2 {
    /**
     * {50, 60, 30, 10, 20, 40} will form a Node Structure as follows
     * 5
     * ├─L─ 3
     * │   ├─L─ 1
     * │   │   └─R─ 2
     * │   └─R─ 4
     * └─R─ 6
     * L: left
     * R: Right
     * Path should be: [4, 3, 1, 2]
     * steps: 3 <- output
     *
     * @param args
     */
    public static void main(String[] args) {
        int i = pathSteps(new int[] {50, 60, 30, 10, 20, 40}, 6, 20, 60);
        System.out.println(i);
    }

    private static int pathSteps(int[] ints, int n, int from, int to) {
        Node root = null;
        Map<Node, Node> allNodes = new HashMap<>();

        for (int i: ints) {
            if (root == null) {
                root = new Node(i);
                allNodes.put(root, root);
            }
            root.addNode(i, allNodes);
        }
        Map<Node, List<Node>> cache = new HashMap<>();

        Node fromN = new Node(from);
        Node toN = new Node(to);

        if (! allNodes.containsKey(fromN) || ! allNodes.containsKey(toN)) {
            return -1;
        }
        fromN = allNodes.get(fromN);
        toN = allNodes.get(toN);

        List<Node> path = traverse(fromN, toN, cache);
        return path.size() - 1;
    }

    private static List<Node> traverse(Node fromN, Node toN, Map<Node, List<Node>> cache) {

        if(cache.containsKey(fromN)) {
            System.out.println("cache Hit: " + fromN);

            return cache.get(fromN);
        }
        System.out.println("visiting: " + fromN);
        if (fromN == null || fromN.visited) {
            return new ArrayList<>();
        }
        if (fromN.equals(toN)) {
            List<Node> target = new ArrayList<>();
            target.add(toN);
            return target;
        }
        fromN.visited = true;

        List<Node> parentWay = new ArrayList<>();
        List<Node> lchildWay = new ArrayList<>();
        List<Node> rchildWay = new ArrayList<>();

        parentWay.addAll(traverse(fromN.parent, toN, cache));
        lchildWay.addAll(traverse(fromN.lchild, toN, cache));
        rchildWay.addAll(traverse(fromN.rchild, toN, cache));

        List<Node> shortest = getShortestList(getShortestList(parentWay, lchildWay), rchildWay);

        cache.put(fromN, shortest);
        if (! shortest.isEmpty()) {
            shortest.add(fromN);
        }
        fromN.visited = false;
        System.out.println(shortest);
        return shortest;
    }

    private static List<Node> getShortestList(List<Node> l1, List<Node> l2 ) {
        List<Node> shortest = null;
        if (l1 != null & l2 != null) {
            if (l1.isEmpty()) {
                shortest = l2;
            } else if (l2.isEmpty()) {
                shortest = l1;
            } else {
                shortest = l1.size() < l2.size() ? l1 : l2;
            }
        } else if (l1 == null) {
            shortest = l2;
        } else if (l2 == null) {
            shortest = l1;
        }
        return shortest;
    }

    private static class Node {
        Node parent;
        Node lchild;
        Node rchild;

        final int value;
        public boolean visited;

        private Node(int value) {
            this.value = value;
        }

        public void addNode(int i, Map<Node, Node> allNodes) {
            if (i > value) {
                if (null == rchild) {
                    rchild = new Node(i);
                    rchild.parent = this;
                    allNodes.put(rchild, rchild);
                } else {
                    rchild.addNode(i, allNodes);
                }
            }
            if (i < value) {
                if (null == lchild) {
                    lchild = new Node(i);
                    lchild.parent = this;
                    allNodes.put(lchild, lchild);
                } else {
                    lchild.addNode(i, allNodes);
                }
            }
        }

        @Override
        public boolean equals(Object obj) {
            return ((Node) obj).value == value;
        }

        @Override
        public int hashCode() {
            return value;
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }
    }
}

Ответ 7

• Найдите наименее распространенного предка (LCA), как и в Q56. См. оба подхода для поиска LCA. Я бы предпочел первый подход, поскольку он хранит путь каждого node, который мы также можем использовать для нахождения расстояния b/w node до LCA
• Теперь подсчитайте количество узлов в пути 1 и пути 2. Всего будет указано количество разделов/вершин (пути 1 Nodes -1) + (Path2 Nodes -1)