C++에서 노드와 조상의 최대 차이

이진 트리의 루트가 있다고 가정하고 서로 다른 노드 A와 B가 있는 최대값 V를 찾아야 합니다. 여기서 V =|A의 값 – B의 값| A는 B의 조상입니다. 따라서 트리가 다음과 같다면 -

그러면 출력은 7이 됩니다. 조상 노드 차이는 [(8 - 3), (7 - 3), (8 - 1), (10-13)]과 같으며 그 중 (8 - 1) =7은 다음과 같습니다. 최대.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 처음에 0으로 정의

• solve()라는 메소드를 정의하면 트리 노드인 currMin 및 currMax가 사용됩니다. 이것은 다음과 같이 작동합니다 -

• 노드가 null이면 반환

• ans :=ans의 최대값, |노드의 값 - currMin|, |노드의 값 - currMax|

• 해결(노드 왼쪽, 노드 값의 최소값과 currMin, 노드 값의 최대값과 currMax)

• 해결(노드 오른쪽, 노드 값의 최소값 및 currMin, 노드 값의 최대값 및 currMax)

• 메인 섹션에서 solve(root, value of root, value of root)를 호출하고 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