101 Symmetric Tree

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

For example, this binary tree[1,2,2,3,4,4,3]is symmetric:

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

But the following[1,2,2,null,3,null,3]is not:

   1
   / \
  2   2
   \   \
   3    3

Iterative

// Symmetric Tree
// 迭代版，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
    bool isSymmetric (TreeNode* root) {
        if (!root) return true;

        stack<TreeNode*> s;
        s.push(root->left);
        s.push(root->right);

        while (!s.empty ()) {
            auto p = s.top (); s.pop();
            auto q = s.top (); s.pop();

            if (!p && !q) continue; //both NULL
            if (!p || !q) return false; // one NULL
            if (p->val != q->val) return false;

            s.push(p->left);
            s.push(q->right);

            s.push(p->right);
            s.push(q->left);
        }

        return true;
    }
};

Recursive

// Symmetric Tree
// 递归版，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (root == nullptr) return true;
        return isSymmetric(root->left, root->right);
    }
    bool isSymmetric(TreeNode *p, TreeNode *q) {
        if (p == nullptr && q == nullptr) return true;   // 终止条件
        if (p == nullptr || q == nullptr) return false;  // 终止条件
        return p->val == q->val      // 三方合并
                && isSymmetric(p->left, q->right)
                && isSymmetric(p->right, q->left);
    }
};

Wrong

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return false;

        queue<TreeNode*> cur, next;
        cur.push(root);

        while(!cur.empty()) {
            vector<int> level;
            while(!cur.empty()) {
                TreeNode* node = cur.front();
                cur.pop();
                level.push_back(node->val);

                if (node->left != nullptr) next.push(node->left);
                if (node->right != nullptr) next.push(node->right);
            }
            //check symmetric in each level
            // Bug!!!!!!!!!!!!!!!!!!!!!!!!!!
            int len = level.size();

            if (len > 1) {
                // check len is even or odd, odd will return false
                if (len % 2 != 0) return false;

                int i = 0;
                int j = len - 1;
                for (; i < len/2; ++i, --j) {
                    if (level[i] != level[j])
                        return false;
                }
            }
            swap(next, cur);
        }
        return true;
    }
};

[1,2,2,null,3,null,3]
   1
   / \
  2   2
   \   \
   3    3

  Output: true
Expected: false

[1, 2, 2, null, 3, 3, null]   True
     1
   /   \
  2     2
   \   / \
   3  3

Revised

// revised
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;

        queue<TreeNode*> cur, next;
        cur.push(root);

        while(!cur.empty()) {
            vector<int> level;
            while(!cur.empty()) {
                TreeNode* node = cur.front();
                cur.pop();
                if(node == nullptr) {
                    level.push_back(-1);
                    continue;
                }
                else
                    level.push_back(node->val);

                if (node->left == nullptr) 
                    next.push(nullptr);
                else
                    next.push(node->left);
                if (node->right == nullptr)
                    next.push(nullptr);
                else
                    next.push(node->right);
            }
            //check symmetric in each level
            int len = level.size();

            if (len > 1) {
                // check len is even or odd, odd will return false
                if (len % 2 != 0) return false;

                int i = 0;
                int j = len - 1;
                for (; i < len/2; ++i, --j) {
                    if (level[i] != level[j])
                        return false;
                }
            }
            swap(next, cur);
        }
        return true;
    }
};