LeetCode 101 Symmetric Tree（对称树）（*）

翻译

给定一个二叉树，检查它是否是它本身的镜像（也就是说，中心对称）。

例如，这个二叉树是对称的：
    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个却不是：
    1
   / \
  2   2
   \   \
   3    3

批注：
如果你能同时用递归和迭代来解决这个问题，这会是加分项。

原文

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.

分析

其实吧，这道题和下面这道题的思路非常的类似，都是从上向下不断的遍历，只不过是比较的对象不一样而已。

LeetCode 110 Balanced Binary Tree（平衡二叉树）（*）

一开始我写了下面这段代码，不过后来发现错了，镜像不是这么回事……下面的代码是每个节点的左右子节点对称，而镜像是对于整个树而言的一种对称。所以继续改改改……

bool isSymmetric(TreeNode* root) {
    if (!root || (!root->left && !root->right)) return true;
    else if (!root->left || !root->right) return false;
    if (root->left->val != root->right->val)
        return false;
    else if (!isSymmetric(root->left) || !isSymmetric(root->right)) return false;
    return true;
}

经过无数次的修改，最终成了如下版本：

bool  isSymmetricIter(TreeNode* r1, TreeNode* r2) {
    if (!r1 && !r2)  return true;
    else if (!r1 || !r2) return false;
    if ((!r1->left && !r2->right && !r1->right && !r2->left)) return true;
    if ((r1->left && r2->right)) {
        if (r1->left->val != r2->right->val)
            return false;
    }
    else if (!r1->left && !r2->right) {}
    else return false;
    if ((r1->right && r2->left)) {
        if (r1->right->val != r2->left->val)
            return false;
    }
    else if (!r1->right && !r2->left) {}
    else return false;

    if (!isSymmetricIter(r1->left, r2->right) || !isSymmetricIter(r1->right, r2->left)) return false;
    return true;
}

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    else if (!root->left && !root->right) return true;
    else if (!root->left || !root->right) return false;
    else if (root->left->val != root->right->val) return false;
    return isSymmetricIter(root->left, root->right);
    return isSymmetricIter(root->left, root->right);
}

后来继续修改修改，让它更简洁一些。

bool  isSymmetricIter(TreeNode* r1, TreeNode* r2) {
    if (!r1 && !r2)  return true;
    else if (!r1 || !r2) return false;
    if (!r1->left && !r2->right && !r1->right && !r2->left) return true;

    if ((r1->left && r2->right)) {
        if (r1->left->val != r2->right->val)
            return false;
    }
    else if (!(!r1->left && !r2->right)) return false;
    if ((r1->right && r2->left)) {
        if (r1->right->val != r2->left->val)
            return false;
    }
    else if (!(!r1->right && !r2->left)) return false;

    if (!isSymmetricIter(r1->left, r2->right) || !isSymmetricIter(r1->right, r2->left)) return false;
    return true;
}

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    return isSymmetricIter(root, root);
}