Evolve from straightforward solution, a review of top solutions


  • 0

    This easy problem can be solved in various ways. From the graph, it is clear that the nodes are symmetric on each level, so a straightforward solution is to check it level by level.

    1. BFS, to check each level, we want to compare the first node with the last one. Since queue does not have random access to the elements, we can just use two vectors to cache the current level and the next level.
        bool isSymmetric(TreeNode* root) {
            vector<TreeNode*> cur(1,root), nxt, *p_cur=&cur, *p_nxt=&nxt;
            while(!p_cur->empty()) {
                int n = p_cur->size();
                for(int i=0;i<=n/2;i++) {
                    TreeNode *l = p_cur->at(i), *r = p_cur->at(n-1-i);
                    if(!l && !r) continue;
                    if(!r || !l || l->val!=r->val) return false;
                }
                for(TreeNode* t:*p_cur) {
                    if(!t) continue;
                    p_nxt->push_back(t->left);
                    p_nxt->push_back(t->right);
                }
                swap(p_cur,p_nxt);
                p_nxt->clear();
            }
            return true;
        }
    

    The above solution caches two levels, we can use a queue and cache one level only. For each level, the nodes are not stored from left to right. Symmetric nodes are pushed and poped simultaneously. So it is like BFS the two mirrors simultaneously.

        bool isSymmetric(TreeNode* root) {
            if(!root) return 1;
            queue<TreeNode*> q({root->left, root->right});
            while(!q.empty()) {
                TreeNode *l = q.front();
                q.pop();
                TreeNode *r = q.front();
                q.pop();
                if(!l && !r) continue;
                if(!l || !r || l->val != r->val) return 0;
                q.push(l->left);
                q.push(r->right);
                q.push(l->right);
                q.push(r->left);
            }
            return 1;
        }
    
    1. DFS. The most interesting part, the queue can be literally replace by a stack and the algorithm becomes DFS. It is like simultaneous DFS of the two mirrors.
        bool isSymmetric(TreeNode* root) {
            if(!root) return 1;
            stack<TreeNode*> stk({root->left, root->right});
            while(!stk.empty()) {
                TreeNode *l = stk.top();
                stk.pop();
                TreeNode *r = stk.top();
                stk.pop();
                if(!l && !r) continue;
                if(!l || !r || l->val != r->val) return 0;
                stk.push(l->left);
                stk.push(r->right);
                stk.push(l->right);
                stk.push(r->left);
            }
            return 1;
        }
    

    DFS can also be implemented recursively.

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

Log in to reply
 

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