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

Follow up: Solve it both recursively and iteratively.

---

本题要判断一棵二叉树是否是镜面对称的，镜面对称就像题中第一个例子，在树中间画一条线，则树的左右两边是镜面对称的。
无论是递归还是迭代的解法，镜面对称的树都需要满足以下三个条件：

1. 左右节点的值相等
2. 左节点的左孩子等于右节点的右孩子
3. 左节点的右孩子等于右节点的左孩子

根据以上的三条规则，可以很容易写出递归版本的代码：

class Solution {
public:
    bool work(TreeNode* left, TreeNode* right)
    {
        if (left == NULL && right == NULL)
            return true;
        if (left == NULL || right == NULL)
            return false;
        bool cond1 = left->val == right->val;
        bool cond2 = work(left->left, right->right);
        bool cond3 = work(left->right, right->left);
        return cond1 && cond2 && cond3;
    }
    bool isSymmetric(TreeNode* root)
    {
        if (root == NULL)
            return true;
        return work(root->left, root->right);
    }
};

本代码提交AC，用时6MS。
迭代的版本中，因为每层都需要判断左右是否镜面对称，所以可以用类似层次遍历的方法，也相当于广度优先遍历。因为是左右两棵子树，所以需要用到两个队列，在节点入队的时候需要注意，因为以上的第2,3个条件，所以如果对左节点的孩子入队顺序是先左后右，那么对右节点的孩子入队顺序就应该是先右后左，这样出队时的顺序才能和2,3条件一致。完整代码如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root)
    {
        if (root == NULL)
            return true;
        queue<TreeNode *> left, right;
        left.push(root->left);
        right.push(root->right);
        while (!left.empty() && !right.empty()) {
            TreeNode *l = left.front(), *r = right.front();
            left.pop();
            right.pop();
            if (l == NULL && r == NULL)
                continue;
            if (l == NULL || r == NULL)
                return false;
            if (l->val != r->val)
                return false;
            left.push(l->left);
            left.push(l->right);
            right.push(r->right);
            right.push(r->left);
        }
        return true;
    }
};

本代码提交AC，用时3MS。

二刷。迭代版本，用一个双端队列也可以解决，就是麻烦一点：

class Solution {
public:
	bool isSymmetric(TreeNode* root) {
		if (root == NULL)return true;
		deque<TreeNode*> q; // deque支持下标访问，而queue不支持
		q.push_back(root);
		while (!q.empty()) {
			int n = q.size();
			int i = 0, j = n - 1;
			bool curans = true;
			while (i < j) {
				if (q[i] != NULL && q[j] != NULL && q[i]->val == q[j]->val) {
					++i;
					--j;
				}
				else if (q[i] == NULL && q[j] == NULL) {
					++i;
					--j;
				}
				else {
					curans = false;
					break;
				}
			}
			if (!curans)return false;
			while (n--) {
				TreeNode* cur = q.front();
				if (cur != NULL) {
					q.push_back(cur->left);
					q.push_back(cur->right);
				}
				q.pop_front();
			}
		}
		return true;
	}
};

本代码提交AC，用时8MS。