圖論應用題 祖孫節點的最大差值絕對值 Max Diff Between Nodes_Leetcode #1026

Aaron Burden on Unsplash

題目敘述

題目會給定我們一棵二元數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:

[1] Maximum Difference Between Node and Ancestor - LeetCode