題目敘述
題目會給定我們一棵二元數Binary Tree的根結點。
問我們任意祖先節點和晚輩節點之間，最大的差值的絕對值是多少?
題目的原文敘述測試範例
Example 1:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
Example 2:
Input: root = [1,null,2,null,0,3]
Output: 3
約束條件
Constraints:
- The number of nodes in the tree is in the range
[2, 5000]. 0 <= Node.val <= 10^5
演算法
因為題目給定的是根結點，所以拜訪順序一定是從上往下走。
這題的關鍵在於如何從上層傳遞資訊給下層的子節點。
題目要求的是任意祖先和晚輩節點之間的最大差值的絕對值，最大差值一定發生在最大值和最小值相減的時候。
因此，我們可以在DFS function中除了放node節點資訊之外，多攜帶兩個參數，分別是low和high代表目前這條路徑所遇到的最小值和最大值，每一次往下遞迴的時候，都攜帶並且更新最小值和最大值。
最後，讓所有探索路徑的最大值-最小值=差值，再取max取得最大的差值，就是最終的答案。
程式碼
class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
def update(node, low, high):
if not node:
return high - low
high = max(high, node.val)
low = min(low, node.val)
return max( update(node.left, low, high), update(node.right, low, high) )
# ------------------------
return update(root, root.val, root.val)
複雜度分析
時間複雜度:
DFS拜訪整張圖，每個節點至多拜訪一次， O(n)。
空間複雜度:
O(n) DFS拜訪整張圖，最大深度發生在整棵樹向左歪斜或者向右歪斜時 = O(n)。
關鍵知識點
這題的關鍵在於如何從上層傳遞資訊給下層的子節點。
題目要求的是任意祖先和晚輩節點之間的最大差值的絕對值，最大差值一定發生在最大值和最小值相減的時候。
Reference:
