Java节点与祖先最大差值问题代码异常排查求助

你的代码只计算了直接父节点与子节点的差值，但题目要求的是任意节点与其所有祖先节点（包括隔代祖先）的最大差值。比如存在这样的树：10 -> 5 -> 3，原代码只会计算10-5=5和5-3=2，但实际上10-3=7才是最大差值，这就是大型测试用例出错的核心原因。

我们需要在遍历树的过程中，记录当前节点所有祖先中的最大值，然后计算当前节点与这个最大值的差值，全程跟踪最大的差值。以下是优化后的代码：

class Tree {
    // 用于跟踪全局最大差值
    private int maxDiffValue;

    //Function to return the maximum difference between any node and its ancestor.
    int maxDiff(Node root) {
        if (root == null) return 0;
        maxDiffValue = Integer.MIN_VALUE;
        // 初始时，祖先的最大值就是根节点的值
        traverse(root, root.data);
        return maxDiffValue;
    }

    private void traverse(Node node, int maxAncestor) {
        if (node == null) return;

        // 计算当前节点与祖先最大值的差值，更新全局最大差值
        int currentDiff = maxAncestor - node.data;
        if (currentDiff > maxDiffValue) {
            maxDiffValue = currentDiff;
        }

        // 更新祖先最大值：当前节点也会成为其子节点的祖先
        int newMaxAncestor = Math.max(maxAncestor, node.data);

        // 递归遍历左右子树
        traverse(node.left, newMaxAncestor);
        traverse(node.right, newMaxAncestor);
    }
}

如果题目要求的是绝对值最大的差值（比如后代值远大于祖先值的情况），则需要同时跟踪祖先的最大值和最小值，计算两种差值的绝对值：

class Tree {
    private int maxDiffValue;

    int maxDiff(Node root) {
        if (root == null) return 0;
        maxDiffValue = Integer.MIN_VALUE;
        traverse(root, root.data, root.data);
        return maxDiffValue;
    }

    private void traverse(Node node, int maxAncestor, int minAncestor) {
        if (node == null) return;

        // 计算当前节点与祖先最值的差值绝对值，更新最大差值
        int diff1 = Math.abs(maxAncestor - node.data);
        int diff2 = Math.abs(minAncestor - node.data);
        maxDiffValue = Math.max(maxDiffValue, Math.max(diff1, diff2));

        // 更新祖先的最值
        int newMax = Math.max(maxAncestor, node.data);
        int newMin = Math.min(minAncestor, node.data);

        traverse(node.left, newMax, newMin);
        traverse(node.right, newMax, newMin);
    }
}

• 不再局限于直接父子节点的差值，覆盖了所有祖先与后代的组合
• 递归过程中传递路径上的最值，确保每个节点都能和所有祖先计算差值
• 时间复杂度为O(n)，每个节点仅遍历一次，完全适配大型测试用例

内容的提问来源于stack exchange，提问作者SEJAL PITHADIA