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

Categories:

题目描述
思路分析
1. 解法一：DFS 维护路径最值（推荐）
相似题目

题目描述

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

思路分析

解法一：DFS 维护路径最值（推荐）

核心思路：

沿根到叶的路径维护当前最小值与最大值。

到达节点时更新答案为 max(|node - min|, |node - max|)。

递归向下传递更新后的最值。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点个数。

空间复杂度：O(h)，其中 h 表示树的高度（递归栈）。

class Solution {
    private int ans = 0;

    public int maxAncestorDiff(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, root.val, root.val);
        return ans;
    }

    private void dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) {
            return;
        }

        // 更新路径上的最小值与最大值
        minVal = Math.min(minVal, node.val);
        maxVal = Math.max(maxVal, node.val);
        ans = Math.max(ans, Math.max(Math.abs(node.val - minVal), Math.abs(node.val - maxVal)));

        dfs(node.left, minVal, maxVal);
        dfs(node.right, minVal, maxVal);
    }
}

func maxAncestorDiff(root *TreeNode) int {
	if root == nil {
		return 0
	}

	ans := 0
	var dfs func(node *TreeNode, minVal int, maxVal int)
	dfs = func(node *TreeNode, minVal int, maxVal int) {
		if node == nil {
			return
		}

		// 更新路径上的最小值与最大值
		if node.Val < minVal {
			minVal = node.Val
		}
		if node.Val > maxVal {
			maxVal = node.Val
		}
		diff1 := node.Val - minVal
		if diff1 < 0 {
			diff1 = -diff1
		}
		diff2 := node.Val - maxVal
		if diff2 < 0 {
			diff2 = -diff2
		}
		if diff1 > ans {
			ans = diff1
		}
		if diff2 > ans {
			ans = diff2
		}

		dfs(node.Left, minVal, maxVal)
		dfs(node.Right, minVal, maxVal)
	}

	dfs(root, root.Val, root.Val)
	return ans
}

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	DFS
543. 二叉树的直径	简单	DFS
124. 二叉树中的最大路径和	困难	DFS
687. 最长同值路径	中等	DFS
112. 路径总和	简单	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/82069309