題目描述

給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對(duì)稱的。

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

但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱的:

    1
   / \
  2   2
   \   \
   3    3

題目解答

遞歸比較的思想：

• 樹對(duì)稱的條件為——根的左子樹的值和右子樹的值成鏡像
• 所以可以采取兩個(gè)遞歸線路的方法，左子樹的左節(jié)點(diǎn)值與右子樹的右節(jié)點(diǎn)值必較；同樣，左子樹的右節(jié)點(diǎn)值與右子樹的左節(jié)點(diǎn)值必較。若是全部相等，則說明該樹對(duì)稱

代碼：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSame(struct TreeNode* left, struct TreeNode* right) {
    if (left == NULL && right == NULL)
        return true;
    else if (left == NULL || right == NULL)
        return false;
    else if (left->val != right->val)
        return false;
    else
        return isSame(left->left, right->right) &&
        isSame(left->right, right->left);
}
bool isSymmetric(struct TreeNode* root) {
    if (root == NULL)
        return true;
    return isSame(root->left, root->right);
}