Трассировка через рекурсивное двоичное дерево LCA

simbanala спросил: 13 июня 2018 в 10:50 в: java

Может кто-то, пожалуйста, помогите мне проследить этот код. Мне сложно отображать обратные рекурсивные вызовы.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }    if (root == p || root == q) {
        return root;
    }    TreeNode l = lowestCommonAncestor(root.left,p,q);
    TreeNode r = lowestCommonAncestor(root.right,p,q);    if (l != null && r != null){
        return root;
    }    return l != null ? l:r;}

1 ответ

mrmichaeldev ответил: 15 июня 2018 в 11:05

Два вызова lowCommonAncestor просто перемещаются по дереву влево, а затем обратно вправо в дереве, это называется глубиной первого поиска. Порядок узлов DFS

Дополнительное видео по вопросу: Трассировка через рекурсивное двоичное дерево LCA

Java Binary Search Tree

12 - Алгоритмы и структуры данных. Двоичные деревья поиска и Декартовы деревья

Бинарное дерево поиска (BST) | Смотрим код | Часть 2