节点与其祖先之间的最大差值
难度:
标签:
题目描述
给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
示例 1：
输入：root = [8,3,10,1,6,null,14,null,null,4,7,13] 输出：7 解释： 我们有大量的节点与其祖先的差值，其中一些如下： |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
示例 2：
输入：root = [1,null,2,null,0,3] 输出：3
提示：
- 树中的节点数在
2到5000之间。 0 <= Node.val <= 105
代码结果
运行时间: 24 ms, 内存: 0.0 MB
/*
* 思路：
* 使用Java Stream来简化递归部分的实现。
* 我们通过流式处理对树进行遍历，并找到节点之间的最大差值。
*/
import java.util.stream.Stream;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int maxDiff = 0;
public int maxAncestorDiff(TreeNode root) {
if (root == null) return 0;
maxDiff = Stream.of(root)
.flatMap(node -> Stream.of(helper(node, node.val, node.val)))
.max(Integer::compareTo)
.orElse(0);
return maxDiff;
}
private int helper(TreeNode node, int minVal, int maxVal) {
if (node == null) return maxDiff;
minVal = Math.min(minVal, node.val);
maxVal = Math.max(maxVal, node.val);
maxDiff = Math.max(maxDiff, Math.abs(maxVal - minVal));
if (node.left != null) helper(node.left, minVal, maxVal);
if (node.right != null) helper(node.right, minVal, maxVal);
return maxDiff;
}
}解释
方法:
这个解法采用了递归的方式，通过深度优先搜索(DFS)遍历整棵树。在遍历过程中，维护两个变量：当前路径上的最大值`high`和最小值`low`。对于每个节点，我们更新这两个值，并递归地计算左右子树的最大祖先差。最终结果是所有子树中祖先差的最大值。我们通过比较当前节点值与`high`和`low`的差值来更新祖先差，确保每次递归返回的是当前子树中的最大祖先差。
时间复杂度:
O(n)
空间复杂度:
O(h)，其中h为树的高度
代码细节讲解
🦆
DFS算法在更新最大值和最小值时，是如何确保这两个值始终正确代表当前节点到根节点路径上的值？
▷🦆
在极端不平衡的二叉树中，递归深度可能达到n。这种情况下是否有可能导致栈溢出？如果是，如何优化以避免这一问题？
▷🦆
为什么选择在每个节点处比较当前节点值与路径上最大最小值的差而不是其他方式？这种方式有何优势？
▷🦆
在递归函数中，如果当前节点是null，为什么返回的是high - low而不是0或其他值？
▷