C++の二分木のいとこ

二分木があり、ルートノードが深さ0にあり、各深さkノードの子が深さk+1にあるとします。

ここで、二分木の2つのノードは、深さが同じで親が異なる場合、いとこと呼ばれます。

ツリーのすべての値は一意であり、ツリー内の2つの異なるノードの値xとyです。値xとyに対応するノードがいとこであるかどうかを確認する必要があります。

したがって、入力が次のような場合

x =5、y =4の場合、出力はtrueになります

これを解決するには、次の手順に従います-

• 1つのマップを定義する

• 1つのキューを定義するq

• ルートをqに挿入

• um [x]：=um [y]：=null

• （qが空ではない）間、-

  • qSize：=qのサイズ

  • qSize> 0の場合（qSizeを1減らします）、-

    を実行します。

    • cur：=qの最初の要素

    • qから要素を削除

    • currの左側が存在する場合、-

      • umにcurの左側の値がある場合、

        • um [curの左側の値]：=cur

      • それ以外の場合

        • curの左側をqに挿入します

      • umにcurの権利の値がある場合、

        • um [curの権利の値]：=cur

      • それ以外の場合

        • カーの権利をqに挿入

    • um[x]またはum[y]がゼロ以外の場合、-

      • um [x]が0、um [y]が0、またはum[x]がum[y]と同じ場合、-

        • falseを返す

      • それ以外の場合

        • trueを返す

• falseを返す

例

理解を深めるために、次の実装を見てみましょう-

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

出力

1