---

前言

本篇繼續講解二叉樹OJ題目之對稱二叉樹

---

對稱二叉樹

題目鏈接：https://leetcode.cn/problems/symmetric-tree/description/


該題要求比較這棵樹是否對稱，對稱，指的是結構對稱并且值也要對稱，即對應節點相等，如上圖示例2中，它的結構并不對稱，因此不可視為對稱樹

再如示例1，結構對稱，并且值也對稱，即對稱節點的值也相同，那么便可視為對稱樹

因為題目告知該樹至少有一個節點，所以比較的自然是根節點的左右子樹，那么我們可以延續判斷兩棵樹是否相同的思路

解決該題有兩種思路

我們以題目示例1的二叉樹作為示例進行講解

第一種思路：
我們將該樹根節點的左子樹記為p樹，右子樹記為q樹，之后翻轉p樹或者q樹中任意一個，得到新的p樹或q樹，最后比較p樹和q樹是否相等即可

翻轉p樹后如圖所示：

此時我們比較p樹和q樹是否相同即可，若為相同樹，則原二叉樹為對稱樹，若不為相同樹則否
代碼實現：

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

第二種思路：
我們將該樹根節點的左子樹記為p樹，右子樹記為q樹，之后比較p樹和q樹是否對稱即可

如第一種思路，我們是將p樹q樹中的一個翻轉后比較是否相同，而該思路則是省去翻轉的步驟，直接比較結構是否對稱，對稱點的值是否相等

例如，我們比較p、q兩樹的根節點是否存在且值相同，若不存在直接返回true，代表該樹對稱，因為根節點的左右子樹均為空；若存在且值相同，則繼續往下執行

此時我們調用的判斷相同樹的函數，唯一不同的一點是我們在該函數中傳參時傳的是p樹的左子樹和q樹的右子樹比較，以及p樹的右子樹和q樹的左子樹比較

如果p樹左子樹與q樹的右子樹相同，說明外側是對稱的

如果p樹右子樹和q樹的左子樹相同，說明內側是對稱的

因此，當p樹的左子樹和q樹的右子樹相同并且p樹的右子樹和q樹的左子樹也相同時，我們可以說該二叉樹是一棵對稱樹

代碼實現：

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