Как это гарантирует, что один узел является предком, а не родным братом?

Question

Я пытаюсь решить этот вопрос LeetCode :

Учитывая корень двоичного дерева, найдите максимальное значение V, для которого существуют разные узлы A и B, гдеV = | A.val - B.val |и A является предком B. (Узел A является предком B, если либо: любой дочерний элемент A равен B, либо любой дочерний элемент A является предком B.)

Один из ответов с высоким голосом выглядит следующим образом:

public int maxAncestorDiff(TreeNode root) {
    return dfs(root, root.val, root.val);
}

public int dfs(TreeNode root, int mn, int mx) {
    if (root == null) return mx - mn;
    mx = Math.max(mx, root.val);
    mn = Math.min(mn, root.val);
    return Math.max(dfs(root.left, mn, mx), dfs(root.right, mn, mx));
}

По сути, это всего лишь предварительный обход дерева.Я не могу переварить, как это гарантирует, что узел A является предком узла B (а не родного брата)?

Answer 1

Давайте разберемся с этим.

Вы правы, что это просто трансверсал предварительного заказа.Важно то, что для каждого узла у нас есть минимальное значение и максимальное значение.Эти значения становятся меньше и больше соответственно, когда мы выполняем итерацию по дереву.В любом конкретном узле мы обновляем mn и mx только значением этого узла.В результате, когда мы передаем mn и mx дочерним элементам, эти значения отражают только узлы в дереве вплоть до текущего узла.

Возможно, эти комментарии лучше проиллюстрируют это:

public int dfs(TreeNode root, int mn, int mx) {

    // this is the base case, at some point mn was encountered and mx was encountered
    // on the path to this node, this is the maximum possible difference along that path
    if (root == null) return mx - mn;

    // on our current path through the tree, update the max / min value we have encountered
    mx = Math.max(mx, root.val);
    mn = Math.min(mn, root.val);

    // the mn and mx at this point are only reflective of this node and it's ancestors
    // integers are immutable so a function call down the line won't change the 
    // mx and mn here, but rather create a new mx and mn at that node
    // we pass the updated mx and mn to the node's children, exploring paths
    // down the tree

    return Math.max(dfs(root.left, mn, mx), dfs(root.right, mn, mx));
}