problem82.cpp

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
  string val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(string x) : val(x), left(NULL), right(NULL) {}
};

class EnchantedMirrorTree {
  string line;
  TreeNode* root;

public:
  void readInput() {
    getline(cin, line);
    if (line.empty()) {
      cout << "!! Invalid Input !!" << endl;
      exit(1);
    }
    root = buildTree();
  }

  TreeNode* buildTree() {
    istringstream iss(line);
    string val;
    vector<string> nodes;
    while (iss >> val)
      nodes.push_back(val);

    if (nodes[0] == "null") return NULL;

    TreeNode* root = new TreeNode(nodes[0]);
    queue<TreeNode*> q;
    q.push(root);

    int i = 1;
    while (!q.empty() && i < nodes.size()) {
      TreeNode* curr = q.front(); q.pop();
      if (nodes[i] != "null") {
        curr->left = new TreeNode(nodes[i]);
        q.push(curr->left);
      }
      i++;
      if (i < nodes.size() && nodes[i] != "null") {
        curr->right = new TreeNode(nodes[i]);
        q.push(curr->right);
      }
      i++;
    }
    return root;
  }

  bool isMirror(TreeNode* left, TreeNode* right) {
    if (!left && !right) return true;
    if (!left || !right || left->val != right->val) return false;

    return isMirror(left->left, right->right) && isMirror(left->right, right->left);
  }

  void display() {
    cout << (isMirror(root->left, root->right) ? "true" : "false") << endl;
  }
};

int main() {
  EnchantedMirrorTree emt;
  emt.readInput();
  emt.display();
  return 0;
}