java - 它如何确保一个节点是祖先节点而不是兄弟节点？

Question

我正在尝试解决 this LeetCode question :

Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B. (A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

highly upvoted answers 之一如下:

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 传递给子级时，这些值仅反射(reflect)树中到当前节点的节点。

也许这些评论会更好地说明这一点:

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