Chênh lệch lớn nhất giữa node và tổ tiên (Maximum Difference Between Node and Ancestor) trong C++

Cho gốc của cây nhị phân, tìm giá trị lớn nhất V = |A.val - B.val| với A là tổ tiên của B (A != B).

Ví dụ: cây cho trước, kết quả 7 (từ |8-1|).

Giải pháp DFS:

• Biến ans = 0.

• Hàm solve(node, currMin, currMax): nếu node null hoặc val=0 return; cập nhật ans = max(ans, |node.val - currMin|, |node.val - currMax|); đệ quy left/right với min/max cập nhật.

• Gọi solve(root, root.val, root.val), trả về ans.

Ví dụ hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val=data; left=NULL; right=NULL; }
};
void insert(TreeNode** root, int val) {
    queue<TreeNode*> q; q.push(*root);
    while (q.size()) {
        TreeNode* temp = q.front(); q.pop();
        if (!temp->left) {
            if (val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0);
            return;
        } else q.push(temp->left);
        if (!temp->right) {
            if (val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0);
            return;
        } else q.push(temp->right);
    }
}
TreeNode* make_tree(vector<int> v) {
    TreeNode* root = new TreeNode(v[0]);
    for (int i=1; i<v.size(); i++) insert(&root, v[i]);
    return root;
}
class Solution {
public:
    int ans;
    void solve(TreeNode* node, int currMin, int currMax) {
        if (!node || node->val == 0) return;
        ans = max({ans, abs(node->val - currMin), abs(node->val - currMax)});
        solve(node->left, min(node->val, currMin), max(node->val, currMax));
        solve(node->right, min(node->val, currMin), max(node->val, currMax));
    }
    int maxAncestorDiff(TreeNode* root) {
        ans = 0;
        solve(root, root->val, root->val);
        return ans;
    }
};
int main() {
    vector<int> v = {8,3,10,1,6,NULL,14,NULL,NULL,4,7,13};
    TreeNode* root = make_tree(v);
    Solution ob;
    cout << (ob.maxAncestorDiff(root));
}

Input

[8,3,10,1,6,null,14,null,null,4,7,13]

Output

7