ความต่างสูงสุดระหว่างโหนดและพ่อบรรพ์ (Maximum Difference Between Node and Ancestor) ใน C++

โจทย์: กำหนด root ของ binary tree หา ค่าสูงสุด V ที่มีโหนด A และ B ต่างกัน โดย V = |A.val - B.val| และ A เป็น ancestor (พ่อบรรพ์) ของ B

ตัวอย่าง

Output: 7 (จาก |8 - 1| = 7)

แนวทางแก้ปัญหา (DFS)

1. กำหนด ans = 0
2. สร้างฟังก์ชัน solve(node, currMin, currMax):
   • ถ้า node null หรือ val==0: return
   • อัปเดต ans = max(ans, |node.val - currMin|, |node.val - currMax|)
   • เรียก solve(left, min(node.val, currMin), max(node.val, currMax))
   • เรียก solve(right, min(node.val, currMin), max(node.val, currMax))
3. เริ่มต้น: เรียก solve(root, root.val, root.val) คืน ans

แนวคิด: ติดตามค่า min และ max บนเส้นทางจาก root ถึงโหนดปัจจุบัน ความต่างสูงสุดจะเกิดจากโหนดปัจจุบันกับ min หรือ max บนเส้นทางนั้น

ตัวอย่างโค้ดเต็ม

#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