1026.节点与其祖先之间的最大差值

目标

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

说明：

• 树中的节点数在 2 到 5000 之间。
• 0 <= Node.val <= 10^5

思路

这道题还是挺直观的，求节点与其祖先之间的最大差值。直接深度优先遍历，记录路径上的最大与最小值，同时计算最大差值即可。

代码

/**
 * @date 2024-04-05 0:13
 */
public class MaxAncestorDiff1026 {

    int res = 0;

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

    public void dfs(TreeNode node, int max, int min) {
        if (node == null) {
            return;
        }
        max = Math.max(node.val, max);
        min = Math.min(node.val, min);
        res = Math.max(res, max - min);
        dfs(node.left, max, min);
        dfs(node.right, max, min);
    }
}

性能