Computer >> Máy Tính >  >> Lập trình >> C ++

Sự khác biệt tối đa giữa nút và tổ tiên trong C ++

Giả sử chúng ta có gốc của cây nhị phân, chúng ta phải tìm giá trị lớn nhất V để tồn tại các nút khác nhau A và B trong đó V =| giá trị của A - giá trị của B | và A là tổ tiên của B. Vì vậy, nếu cây giống -

Sự khác biệt tối đa giữa nút và tổ tiên trong C ++


Khi đó đầu ra sẽ là 7. Sự khác biệt về nút tổ tiên như [(8 - 3), (7 - 3), (8 - 1), (10 - 13)], trong số đó là (8 - 1) =7 là tối đa.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • ban đầu xác định ans 0

  • định nghĩa một phương thức có tên là giải quyết (), phương thức này sẽ lấy nút cây, currMin và currMax. Điều này sẽ hoạt động như sau -

  • nếu nút là null, thì trả về

  • ans:=tối đa ans, | giá trị của nút - currMin |, | giá trị của nút - currMax |

  • giải quyết (bên trái của nút, tối thiểu của giá trị nút và currMin, tối đa của giá trị nút và currMax)

  • giải quyết (bên phải của nút, tối thiểu của giá trị nút và currMin, tối đa của giá trị nút vàcurrMax)

  • Trong phần chính, hãy gọi giải quyết (gốc, giá trị của gốc, giá trị của gốc) và trả về ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

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

Đầu vào 

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

Đầu ra 

7