LeetCode Symmetric Tree: DFS and Iterative Solution

Overview

This LeetCode Symmetric Tree Problem could be converted into the same tree between original and its mirror (DFS). The iterative method is level order.

LeetCode Symmetric Tree Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

DFS Solution

For the recursive solution, it is simple, just DFS regularly over the tree and at the same time perform another DFS starting from the right child of each node (recursively), check whether the current nodes of the two traversals are exactly same or not. Actually it just becomes to same problem to decide if the two trees the original one and the mirror one are the same as in the LeetCode Same Tree problem which I discussed here: “LeetCode Same Tree: DFS, 3 Lines of Code

Iterative Solution

For the iterative one, actually it is level order traversal, for each level, keep all the nodes including the NULL nodes in the queue, and check whether the queue is in palindrome format or not, the source code accepted by the LeetCode OJ to pass this Symmetric Tree problem is as follows:

bool iterativeSymmetricTree(TreeNode *root) {
        if(!root) return true;
        vector<TreeNode *>  q[2];
        int qid1 = 0;
        int qid2 = 1;

        q[qid1].push_back(root);
        while( !q[qid1].empty() || ! q[qid2].empty() ) {
            int len = q[qid1].size();
            for(int i = 0; i < len; ++i) {
                int other = len - 1 - i;
                if(NULL == q[qid1][i] && NULL == q[qid1][other] )
                    continue;
                if(NULL != q[qid1][i] && NULL != q[qid1][other] ) {
                    if( q[qid1][i]->val != q[qid1][other]->val ) {
                        return false;
                    }
                    q[qid2].push_back( q[qid1][i]->left );
                    q[qid2].push_back( q[qid1][i]->right);
                    continue;
                }
                return false; //
            }
            q[qid1].clear();
            qid1 = !qid1; qid2 = !qid2;
        }
        return true;
    }

Summary

I just discussed both the recursive (DFS) and iterative (lever order traversal) solutions to solve the LeetCode Symmetric Tree Problem. Please feel free the share your comments and let me know if there is anything incorrect here.

Written on April 20, 2013