Symmetric Tree

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

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

Solution:

The following codes pass LeetCode Online Large Judge.

Recursive solution is trivial.

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return true;
        else return helper(root->left, root->right);
    }
    bool helper(TreeNode *left, TreeNode *right) {
        if (left != NULL && right != NULL)
            return left->val == right->val &&
                helper(left->left, right->right) &&
                helper(left->right, right->left);
        else
            return left == NULL && right == NULL;
    }
};

Iterative solution: first use breadth first search to print the tree in level order. Then check each level and see whether it is symmetric or not.

The solution for iteratively printing the tree in level order can be found in here. The idea is to use two queues store the current level and the next level, and iteratively print out the nodes' value in each level.

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > list = LevelOrder(root);
        for (int i = 0; i < list.size(); i++) {
            if (!check(list[i])) return false;
        }
        return true;
    }
    
    bool check(vector<int> v) {
        int i = 0, j = v.size() - 1;
        while(i < j) {
            if (v[i] != v[j]) return false;
            i++;
            j--;
        }
        return true;
    }

    vector<vector<int> > LevelOrder(TreeNode *root) {
        vector<vector<int> > results;
        vector<int> tmp;
        if (!root) return results;
        queue<TreeNode*> currentLevel, nextLevel;
        currentLevel.push(root);
        while (!currentLevel.empty()) {
            TreeNode *currNode = currentLevel.front();
            currentLevel.pop();
            if (currNode) {
                tmp.push_back(currNode->val);
                nextLevel.push(currNode->left);
                nextLevel.push(currNode->right);
            }
            else
                tmp.push_back(NULL);
            if (currentLevel.empty()) {
                results.push_back(tmp);
                tmp.clear();
                swap(currentLevel, nextLevel);
            }
        }
        return results;
    }
};

Another dummy solution is to use previous level order (recursive) solution first. That is my first thought, although it also passes large judge, it is still recursive and much complicated than the recursive solution here. So I will omit it.

Updates: for iterative solution, we push NULL for an integer vector, which is actually push 0. We have to store the NULLs in the tree to check whether it is symmetric or not, but if we use 0 instead of NULL, there might be some errors for special cases although we pass the large judge. The following code, which uses another bool vector which only stores whether this location is empty or not, is one possible solution.

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<bool> > nulls;
        vector<vector<int> > list = LevelOrder(root, nulls);
        for (int i = 0; i < list.size(); i++) {
            if (!check(list[i], nulls[i])) return false;
        }
        return true;
    }
    
    bool check(vector<int> v, vector<bool> n) {
        int i = 0, j = v.size() - 1;
        while(i < j) {
            if (v[i] != v[j] || n[i] != n[j]) return false;
            i++;
            j--;
        }
        return true;
    }

    vector<vector<int> > LevelOrder(TreeNode *root, vector<vector<bool> > &nulls) {
        vector<vector<int> > results;
        vector<int> tmp;
        vector<bool> tmp_n;
        if (!root) return results;
        queue<TreeNode*> currentLevel, nextLevel;
        currentLevel.push(root);
        while (!currentLevel.empty()) {
            TreeNode *currNode = currentLevel.front();
            currentLevel.pop();
            if (currNode) {
                tmp.push_back(currNode->val);
                tmp_n.push_back(false);
                nextLevel.push(currNode->left);
                nextLevel.push(currNode->right);
            }
            else {
                tmp.push_back(NULL);
                tmp_n.push_back(true);
            }
            if (currentLevel.empty()) {
                if (!nextLevel.empty()) {
                    results.push_back(tmp);
                    nulls.push_back(tmp_n);
                }
                tmp.clear();
                tmp_n.clear();
                swap(currentLevel, nextLevel);
            }
        }
        return results;
    }
};