題目
給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。
1
/
2 2
/ \ /
3 4 4 3
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:
1
/
2 2
\
3 3
進階：
你可以運用遞歸和迭代兩種方法解決這個問題嗎？
思路一，超時
層序遍歷，然后如果該結點是空結點，往該層子數組中填0，否則填val；
當此層所有結點都被遍歷了(包括空結點)，觀察子數組是否對稱。
然后更新queue，如果該結點為空結點，則它的子結點也是空結點，如果該結點不是空結點，它的子結點根據真實情況填，如果為空也填入NULL。
不過這樣好像超時了，也就無法驗證了。
退出循環的條件是，該層的所有結點都是空結點
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL) que.push(root);while(1){//該層結點元素個數 = 該層隊列元素int size = que.size();vector<int> vec;int null_times=0;//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();if(node!=NULL) {vec.push_back(node->val);//將左右孩子結點入隊列，作為下一層的元素if(node->left!=NULL) que.push(node->left);else que.push(NULL);if(node->right!=NULL) que.push(node->right);else que.push(NULL);}else{null_times++;vec.push_back(-2147483648);//將左右孩子結點入隊列，作為下一層的元素que.push(NULL);que.push(NULL);} }if(null_times == size) break;int vecsize=vec.size();for(int j=0;j<vecsize/2+1;j++){if(vec[j]!=vec[vecsize-1-j]) return false;}}return true;}
};
思路二，構造翻轉二叉樹，判斷是否相同
先構造一棵反轉二叉樹，然后按順序遍歷這兩棵樹，判斷是否相同。
Leetcode226. 翻轉二叉樹(遞歸、迭代、層序三種解法)
LeetCode 100. 相同的樹 思考分析
不過此處有一個問題，我們當時翻轉二叉樹的操作是在輸入的二叉樹上進行修改的。這樣如果直接isSameTree(root,invertTree(root));
得到的結果都是true。所以我們需要先深復制一個新的二叉樹，然后在新的二叉樹上完成翻轉操作，然后將翻轉后的二叉樹與原本的二叉樹進行判斷。
關于深復制一棵二叉樹：
LintCode 375. 克隆二叉樹(深復制)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size = que.size();for(int i =0;i<size;i++){TreeNode* node = que.front();que.pop();TreeNode* tmp;tmp = node->left;node->left = node->right;node->right = tmp;//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return root;}bool isSameTree(TreeNode* p, TreeNode* q) {if(p && q){if(p->val == q->val){return isSameTree(p->right,q->right) && isSameTree(p->left,q->left);}else{return false;} }else if(!p && !q){return true;}return false;}TreeNode * preorder(TreeNode * root){if(root==NULL) return NULL;TreeNode * ans;ans=new TreeNode(root->val);if(root->left!=NULL){ans->left=preorder(root->left);}if(root->right!=NULL){ans->right=preorder(root->right);}return ans;}bool isSymmetric(TreeNode* root) {TreeNode *roota;roota=preorder(root);return isSameTree(root,invertTree(roota));}
};
參考其他思路
之前的構造的思路會導致空間嚴重浪費，并且時間耗費也較多。
關于二叉樹是否對稱，我們要比較的是根結點的左子樹與右子樹是不是相互翻轉的。遞歸遍歷的時候要同時遍歷兩棵樹，比較兩棵子樹的里側和外側元素是否相同。
本題的遍歷順序為后序遍歷，因為要通過遞歸函數的返回值來判斷兩個子樹的內測結點與外側結點是否相等。
一棵樹遍歷順序為左右中，另一棵樹遍歷順序是右左中。這里可以理解為一種回溯的思想。
遞歸法
1、確定遞歸地參數和返回值
參數：該結點的左子樹結點、右子樹結點
返回值：bool類型
bool compare(TreeNode* left,TreeNode* right)
2、確定終止條件
1、左右都為空，返回true
2、左右只有一個為空，返回false
3、左右結點均不為空，比較結點數值，不相同返回false
4、左右結點均不為空，數值相同返回true
if(left == NULL && right==NULL) return true;
else if(left!=NULL && right==NULL) return false;
else if(right!=NULL && left==NULL) return false;
else if(left->val != right->val) return false;3、確定單層遞歸邏輯
處理左右結點皆不為空且數值相同的情況。
1、比較二叉樹外側是否對稱：傳入左結點的左孩子，右結點的右孩子。
2、比較內側是否對稱，傳入左結點的右孩子，右結點的左孩子。
3、如果左右都對稱就返回true，否則返回false
bool outside = compare(left->left,right->right);
bool inside = compare(left->right,right->left);
bool isSame = outside && inside;
return isSame
完整代碼
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool compare(TreeNode* left,TreeNode* right){if(left == NULL && right==NULL) return true;else if(left!=NULL && right==NULL) return false;else if(right!=NULL && left==NULL) return false;else if(left->val != right->val) return false;bool outside = compare(left->left,right->right); bool inside = compare(left->right,right->left);bool isSame = outside && inside; return isSame;}bool isSymmetric(TreeNode* root) {if(root == NULL) return true;return compare(root->left,root->right);}
};
迭代法
這一題的本質是判斷兩個樹是否相互翻轉，并非簡單的遍歷。這里可以使用隊列來比較兩個樹(根結點的左右子樹)是否相互翻轉。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {if(root == NULL) return true;queue<TreeNode*> que;que.push(root->left); //將左子樹頭結點加入隊列que.push(root->right); //將右子樹頭結點加入隊列while(!que.empty()) //判斷兩個樹是否翻轉{TreeNode* leftNode = que.front();que.pop();TreeNode* rightNode = que.front();que.pop();if(!leftNode && !rightNode) {//左右結點均為空，說明此時是對稱的continue;}//左右一個結點不為空，或者都不為空但是數值不同，返回falseif((!leftNode || !rightNode || (leftNode->val!=rightNode->val))){return false;}//外側que.push(leftNode->left); //左左que.push(rightNode->right); //右右//內側que.push(leftNode->right);que.push(rightNode->left);}return true;}
};
)
