Last Updated on 2022-12-09 by Clay
題目
Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.
A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.
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 <= 105
題目會輸入一顆二元搜索樹（BST），然後要求我們返回節點和祖先之間最大的差距值。要注意的是，不能橫跨不同的子樹，比方說把左子樹底下的節點拿去計算跟右子樹前一層的節點去計算，這樣就不算是祖先/子代的關係了。
另一個要注意的是，我們計算的差距不局限於當前節點的『子節點』，實際上，只要是子代延伸出去的都可以去計算，比方說根節點也可以拿來計算跟第 100 層底下葉子節點的差距。
解題思路
陣列儲存當前最大、最小節點
我第一感是使用一個陣列把當前可能存在的最大、最小值儲存起來，用來計算跟當前節點的差距是否會出現最大的差距值。然後在下一層 DFS 走訪結束後，彈出當前陣列所儲存的尾端值。
複雜度
| Time Complexity | O(n) |
| Space Complexity | O(n) |
C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void DFS(TreeNode* root, vector<int>& maxValSeq, vector<int> minValSeq, int& maxDiff) {
// Base case
if (!root) {
return;
}
// Update maximum difference
maxDiff = max(maxDiff, abs(maxValSeq.back()-root->val));
maxDiff = max(maxDiff, abs(minValSeq.back()-root->val));
// Update sequence
if (root->val > maxValSeq.back()) {
maxValSeq.push_back(root->val);
}
else {
maxValSeq.push_back(maxValSeq.back());
}
if (root->val < minValSeq.back()) {
minValSeq.push_back(root->val);
}
else {
minValSeq.push_back(minValSeq.back());
}
// DFS
DFS(root->left, maxValSeq, minValSeq, maxDiff);
DFS(root->right, maxValSeq, minValSeq, maxDiff);
// Pop
maxValSeq.pop_back();
minValSeq.pop_back();
}
int maxAncestorDiff(TreeNode* root) {
vector<int> maxValSeq({root->val});
vector<int> minValSeq({root->val});
int maxDiff = 0;
DFS(root->left, maxValSeq, minValSeq, maxDiff);
DFS(root->right, maxValSeq, minValSeq, maxDiff);
return maxDiff;
}
};優化
後來我發現我並不需要建立陣列儲存當前值。如果我使用 DFS 的方式去遞迴，我可以只存當前的最大值與最小值即可。因為當前的最大值與最小值，本來就只會在當前遞迴的函式中存在，我沒有必要把陣列傳遞到下一層中。
複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
這樣一來，改進最多的就是不需要儲存陣列資訊，所以可以僅使用 O(1) 的空間就完成。
C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void DFS(TreeNode* root, int currMax, int currMin, int& maxDiff) {
// Base case
if (!root) {
return;
}
// Update maximum difference
maxDiff = max(maxDiff, abs(currMax-root->val));
maxDiff = max(maxDiff, abs(currMin-root->val));
// Update sequence
currMax = max(root->val, currMax);
currMin = min(root->val, currMin);
// DFS
DFS(root->left, currMax, currMin, maxDiff);
DFS(root->right, currMax, currMin, maxDiff);
}
int maxAncestorDiff(TreeNode* root) {
int maxDiff = 0;
DFS(root->left, root->val, root->val, maxDiff);
DFS(root->right, root->val, root->val, maxDiff);
return maxDiff;
}
};Python 範例程式碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def DFS(self, root: Optional[TreeNode], curr_max: int, curr_min: int) -> None:
# Base case
if not root:
return
# Update
self.max_diff = max(self.max_diff, abs(curr_max-root.val), abs(curr_min-root.val))
curr_max = max(curr_max, root.val)
curr_min = min(curr_min, root.val)
# DFS
self.DFS(root.left, curr_max, curr_min)
self.DFS(root.right, curr_max, curr_min)
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
self.max_diff = 0
self.DFS(root.left, root.val, root.val)
self.DFS(root.right, root.val, root.val)
return self.max_diff