[LeetCode 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

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

Diffculty
Easy

Similar Problems
[LeetCode 100] Same Tree Easy

Analysis

Solutions

解法一：递归

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;
        } else if (p == nullptr || q == nullptr) {
            return false;
        }
        return p->val == q->val && isSymmetric(p->left, q->right) && isSymmetric(p->right, q->left);
    }
};

解法二： 迭代

考虑用队列，每次 add 两个对应的结点。 如果队列长度为 0，则退出循环；否则取出队列中的两个结点，对值进行判断。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        queue<TreeNode*> que;
        if (root->left == nullptr && root->right == nullptr) {
            return true;
        } else if (root->left == nullptr || root->right == nullptr) {
            return false;
        } else {
            que.push(root->left);
            que.push(root->right);
        }
        while (que.size() != 0) {
            TreeNode* p = que.front(); que.pop();
            TreeNode* q = que.front(); que.pop();
            if (p->val != q->val) {
                return false;
            }
            if (p->left == nullptr && q->right == nullptr) {
                // do nothing
            } else if (p->left == nullptr || q->right == nullptr) {
                return false;
            } else {
                que.push(p->left);
                que.push(q->right);
            }
            if (p->right == nullptr && q->left == nullptr) {
                // do nothing
            } else if (p->right == nullptr || q->left == nullptr) {
                return false;
            } else {
                que.push(p->right);
                que.push(q->left);
            }
        }
        return true;
    }
};