难度: Medium
给定二叉树的根节点 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
class Solution(object):
def maxAncestorDiff(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
return self.helper(root, root.val, root.val)
def helper(self, node, high, low):
if not node:
return high - low
high = max(high, node.val)
low = min(low, node.val)
return max(self.helper(node.left, high, low), self.helper(node.right,high,low))
这个解法采用了递归的方式，通过深度优先搜索(DFS)遍历整棵树。在遍历过程中，维护两个变量：当前路径上的最大值`high`和最小值`low`。对于每个节点，我们更新这两个值，并递归地计算左右子树的最大祖先差。最终结果是所有子树中祖先差的最大值。我们通过比较当前节点值与`high`和`low`的差值来更新祖先差，确保每次递归返回的是当前子树中的最大祖先差。
时间复杂度: O(n)
空间复杂度: O(h)，其中h为树的高度
class Solution(object):
def maxAncestorDiff(self, root):
\"\"\"
:type root: TreeNode
:rtype: int
如果根节点为空，直接返回0
\"\"\"
if not root: return 0
return self.helper(root, root.val, root.val)
def helper(self, node, high, low):
\"\"\"
递归函数用于计算最大祖先差
:param node: 当前节点
:param high: 当前路径上的最大值
:param low: 当前路径上的最小值
:return: 返回当前子树中的最大祖先差
\"\"\"
if not node:
return high - low
high = max(high, node.val)
low = min(low, node.val)
返回左右子树中的最大祖先差
return max(self.helper(node.left, high, low), self.helper(node.right, high, low))
在DFS算法中，每次递归调用时传递当前路径上的最大值和最小值。对于每个节点，这些值在递归调用前被更新：最大值更新为当前节点值和传递来的最大值中的较大者，最小值更新为较小者。这种方法确保了每次递归调用都准确地携带了从根节点到当前节点路径上的最大值和最小值。由于每次递归都是独立的函数调用，更新操作不会影响到其他路径的计算。
是的，在最坏情况下，即二叉树退化为链表时，递归深度可能达到n，可能导致栈溢出。为了避免这种情况，可以采用迭代方法结合显式栈来进行DFS，这样可以手动控制栈的深度，防止系统栈溢出。此外，采用广度优先搜索(BFS)也是一种替代方案，BFS使用队列进行层次遍历，不会因为树的深度过大而导致栈溢出。
选择在每个节点比较当前节点值与路径上最大最小值的差，是因为这种方式直接反映了从根节点到当前节点的路径中可能的最大差值，这是解题目的直接需求。此外，这种方法只需遍历树一次即可计算出结果，效率高。比较当前节点与最大最小值也简化了逻辑，避免了复杂的状态管理和回溯，使得代码更简洁易于理解。
当递归到null节点时，意味着已经到达了叶子节点的子节点，此时的high和low代表了该路径上的最大值和最小值。返回high - low可以得到该路径上可能的最大差值。如果返回0或其他值，则无法正确计算出从根到叶子节点的最大差值，因此返回high - low是为了确保能够正确地计算出每个路径的最大差异。