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

问题1026 节点与其祖先之间的最大差值 ★★☆☆☆

https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/

题目要求并不难理解，翻译一下，从root到每个叶子节点有一条path，这条path上最大值和最小值有一个差，现在要计算的是所有path中差最大的那一条对应的差是多少。

最直接粗暴的想法就是做路径遍历嘛，遍历所有path，每遍历完一条path，计算一下当前path中最大值和最小值的差，并维护最大差，当遍历完所有path后，即得到了最终答案。

	public int maxAncestorDiff(TreeNode root) {
		List<TreeNode> path = new ArrayList<>();
		path.add(root);

		return dfs(root, path, 0);
	}

	private int dfs(TreeNode cur, List<TreeNode> path, int maxDiff) {
		if (cur.left == null
			&& cur.right == null) {
			int pathMaxDiff = pathMaxDiff(path);
            return Math.max(pathMaxDiff, maxDiff);
		}

		if (cur.left != null) {
			path.add(cur.left);
			maxDiff = dfs(cur.left, path, maxDiff);
			path.remove(path.size() - 1);
		}
		if (cur.right != null) {
			path.add(cur.right);
			maxDiff = dfs(cur.right, path, maxDiff);
			path.remove(path.size() - 1);
		}

		return maxDiff;
	}

	private int pathMaxDiff(List<TreeNode> path) {
		int max = path.get(0).val, min = path.get(0).val;
		for (TreeNode node : path) {
			if (node.val > max) {
				max = node.val;
			}
			if (node.val < min) {
				min = node.val;
			}
		}

		return max - min;
	}

路径遍历的解法我觉得在思路和实现上都很好理解，但是效率较差，确实，每次遍历到叶子节点，还要遍历当前path来计算最大差。那么有没有办法能优化呢？官方题解的解法我看了个云里雾里，但是有一点启发了我，那就是能不能把当前path省略，直接动态维护的就是当前path的节点最大值和最小值，尝试了一下，OK的，时间效率也好了很多。另外，相比官方题解，我觉得下面的代码更好理解。

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

	private int dfs(TreeNode cur, int max, int min, int maxDiff) {
		if (cur == null) {
			return maxDiff;
		}

		max = Math.max(cur.val, max);
		min = Math.min(cur.val, min);
		maxDiff = Math.max(maxDiff, max - min);

		if (cur.left == null
			&& cur.right == null) {
			return maxDiff;
		}

		if (cur.left != null) {
			maxDiff = dfs(cur.left, max, min, maxDiff);
		}
		if (cur.right != null) {
			maxDiff = dfs(cur.right, max, min, maxDiff);
		}

		return maxDiff;
	}

在 LeetCode 查看