C++ 3ms using map


  • 0
    P

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

    class Solution {
    public:
    	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;
    			else
    				if (itr->second == symitr->second)	// if symmetric node has a different val, erase it
    					mapright.erase(symitr);
    				else
    					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.