leetcode 1026. Maximum Difference Between Node and Ancestor [Medium]

題目敘述

給一棵二元樹，回傳某個節點與其任意祖先節點之間的最大差值（絕對值）。

解題紀錄

DFS

用 DFS 尋訪每個節點，同時記錄從 root 到當前節點路徑上的最大值和最小值，最大差值就是 max - min。

class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        return get_max_different(root, root->val, root->val);
    }
    
    int get_max_different(TreeNode *root, int maxv, int minv) {
        if (!root) return maxv - minv;
        
        maxv = max(maxv, root->val);
        minv = min(minv, root->val);
        
        return max(get_max_different(root->left, maxv, minv), get_max_different(root->right, maxv, minv));
    }
};

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
static auto _ = [] () {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();