C++ 3ms using map

  • 0

    Maps probably use more space than queues but it performed faster somehow than my queue solution.

    class Solution {
    	bool isSymmetric(TreeNode* root) {
    		if (!root) return true;
    		// put left side in a map // <position, number>
    		unordered_map<int, int> mapleft, mapright;
    		mapNodes(root->left, mapleft, 1),
    		mapNodes(root->right, mapright, 2);
    		// iterating through left side, check right side, symmetric at the same left
    		for (auto itr = mapleft.begin(); itr != mapleft.end(); itr++) {
    			// look for the symmetric node. if found, erase it
    			int pos = itr->first;
    			int d = log2(pos + 1);
    			int start = pow(2, d) - 1;
    			int end = 2 * start;
    			int sympos = end - pos + start;
    			// now check if sympos exists in mapright and has the same value. if so, erase it
    			auto symitr = mapright.find(sympos);
    			if (symitr == mapright.end())			// if symmetric position has no node
    				return false;
    				if (itr->second == symitr->second)	// if symmetric node has a different val, erase it
    					return false;
    		// mapright should be empty, after mapleft traversal removed all symmetric nodes
    		if (mapright.empty())
    			return true;
    		return false;
    	void mapNodes(TreeNode *p, unordered_map<int, int> &ht, int pos) {
    		if (!p) return;
    		// preorder traversal
    		ht[pos] = p->val;
    		mapNodes(p->left, ht, pos * 2 + 1);
    		mapNodes(p->right, ht, pos * 2 + 2);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.