सी++ में नोड और पूर्वज के बीच अधिकतम अंतर

मान लीजिए कि हमारे पास एक बाइनरी ट्री की जड़ है, हमें अधिकतम मान V ज्ञात करना है जिसके लिए अलग-अलग नोड A और B मौजूद हैं जहाँ V =| A का मान - B का मान | और A, B का पूर्वज है। इसलिए यदि पेड़ जैसा है -

तब आउटपुट 7 होगा। पूर्वज नोड अंतर [(8 - 3), (7 - 3), (8 - 1), (10-13)] की तरह हैं, उनमें से (8 - 1) =7 है अधिकतम।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• प्रारंभ में उत्तर को परिभाषित करें

• हल () नामक एक विधि को परिभाषित करें, यह ट्री नोड, currMin और currMax लेगा। यह इस प्रकार कार्य करेगा -

• यदि नोड शून्य है, तो वापस लौटें

• उत्तर:=अधिकतम उत्तर, |नोड का मान - currMin|, |नोड का मान - currMax|

• हल करें (नोड के बाएं, न्यूनतम नोड मान और currMin, अधिकतम नोड मान और currMax)

• हल करें (नोड का अधिकार, न्यूनतम नोड मान और currMin, अधिकतम नोड मान और currMax)

• मुख्य भाग में, कॉल सॉल्व (रूट, रूट का मान, रूट का मान), और रिटर्न ans

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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;
   }
};
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));
}

इनपुट

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

आउटपुट

7