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

2022-01-01 71 words One minute

Contents

題目敘述

給一棵二元樹，回傳某個節點與其祖先節點的最大的差(絕對值)。

解題紀錄

DFS

用 DFS 尋訪每個節點，並且順便紀錄到這個節點之前的 max, min value，這樣子最大的差就是 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;}();