LeetCode 101 Symmetric Tree（對稱樹）（*）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50554857

翻譯

給定一個二叉樹，檢查它是否是它本身的鏡像（也就是說，中心對稱）。

例如，這個二叉樹是對稱的：
    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);
}