C++ 이진 트리의 사촌

<시간/>

이진 트리가 있고 루트 노드가 깊이 0에 있고 각 깊이 k 노드의 자식이 깊이 k+1에 있다고 가정합니다.

여기서 이진 트리의 두 노드는 깊이가 같지만 부모가 다른 경우 사촌이라고 합니다.

트리의 모든 값은 고유하며 트리에 있는 두 개의 서로 다른 노드의 x 및 y 값은 고유합니다. x, y 값에 해당하는 노드가 사촌인지 확인해야 합니다.

따라서 입력이 다음과 같으면

C++ 이진 트리의 사촌

x =5, y =4이면 출력은 true가 됩니다.

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

하나의 맵 정의 um
하나의 대기열 정의 q
루트를 q에 삽입
음[x] :=음[y] :=널
동안(q가 비어 있지 않음) -
를 수행합니다.
- qSize :=q의 크기
- qSize> 0인 동안(qSize를 1만큼 감소) 다음을 수행합니다. -
  - cur :=q의 첫 번째 요소
  - q에서 요소 삭제
  - curr의 왼쪽이 있으면 -
    - um이 cur의 왼쪽 값을 가지면
      - um[cur 왼쪽의 값] :=cur
    - 그렇지 않으면
      - q에 cur의 왼쪽 삽입
    - um에 cur의 값이 있으면
      - um[cur 오른쪽 값] :=cur
    - 그렇지 않으면
      - q에 cur의 오른쪽 삽입
  - um[x] 또는 um[y]가 0이 아니면 -
    - um[x]가 0이거나 um[y]가 0이거나 um[x]가 um[y]와 같으면 -
      - 거짓을 반환
    - 그렇지 않으면
      - true를 반환
거짓을 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data) {
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
public:
   bool isCousins(TreeNode *root, int x, int y) {
      unordered_map<int, TreeNode *> um;
      queue<TreeNode *> q;
      q.push(root);
      um[x] = um[y] = NULL;
      while (!q.empty()) {
         int qSize = q.size();
         while (qSize-- > 0) {
            auto cur = q.front();
            q.pop();
            if (cur->left && cur->left->val != 0)
               if (um.count(cur->left->val))
                  um[cur->left->val] = cur;
               else
                  q.push(cur->left);
            if (cur->right && cur->right->val != 0)
               if (um.count(cur->right->val))
                  um[cur->right->val] = cur;
               else
                  q.push(cur->right);
         }
         if (um[x] or um[y])
            if (!um[x] or !um[y] or um[x] == um[y])
               return false;
            else
               return true;
      }
      return false;
   }
};
main() {
   Solution ob;
   TreeNode *root = new TreeNode(1);
   root->left = new TreeNode(2); root->right = new TreeNode(3);
   root->left->right = new TreeNode(4); root->right->right = new TreeNode(5);
   cout << (ob.isCousins(root, 5, 4));
}

입력

TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2); root->right = new TreeNode(3);
root->left->right = new TreeNode(4); root->right->right = new
TreeNode(5);
cout << (ob.isCousins(root, 5, 4));