題目

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [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

進(jìn)階：
你可以運(yùn)用遞歸和迭代兩種方法解決這個問題嗎？

思路一，超時

層序遍歷，然后如果該結(jié)點(diǎn)是空結(jié)點(diǎn)，往該層子數(shù)組中填0，否則填val；
當(dāng)此層所有結(jié)點(diǎn)都被遍歷了(包括空結(jié)點(diǎn))，觀察子數(shù)組是否對稱。
然后更新queue，如果該結(jié)點(diǎn)為空結(jié)點(diǎn)，則它的子結(jié)點(diǎn)也是空結(jié)點(diǎn)，如果該結(jié)點(diǎn)不是空結(jié)點(diǎn)，它的子結(jié)點(diǎn)根據(jù)真實(shí)情況填，如果為空也填入NULL。
不過這樣好像超時了，也就無法驗(yàn)證了。
退出循環(huán)的條件是，該層的所有結(jié)點(diǎn)都是空結(jié)點(diǎn)

/*** 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){//該層結(jié)點(diǎn)元素個數(shù) = 該層隊列元素int size = que.size();vector<int> vec;int null_times=0;//這里要使用固定大小的size，不能使用que.size(),因?yàn)樵谔幚碇衠ue.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結(jié)點(diǎn)送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結(jié)果que.pop();if(node!=NULL) {vec.push_back(node->val);//將左右孩子結(jié)點(diǎn)入隊列，作為下一層的元素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);//將左右孩子結(jié)點(diǎn)入隊列，作為下一層的元素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;} };

思路二，構(gòu)造翻轉(zhuǎn)二叉樹，判斷是否相同

先構(gòu)造一棵反轉(zhuǎn)二叉樹，然后按順序遍歷這兩棵樹，判斷是否相同。
Leetcode226. 翻轉(zhuǎn)二叉樹(遞歸、迭代、層序三種解法)
LeetCode 100. 相同的樹 思考分析
不過此處有一個問題，我們當(dāng)時翻轉(zhuǎn)二叉樹的操作是在輸入的二叉樹上進(jìn)行修改的。這樣如果直接isSameTree(root,invertTree(root));
得到的結(jié)果都是true。所以我們需要先深復(fù)制一個新的二叉樹，然后在新的二叉樹上完成翻轉(zhuǎn)操作，然后將翻轉(zhuǎn)后的二叉樹與原本的二叉樹進(jìn)行判斷。
關(guān)于深復(fù)制一棵二叉樹：
LintCode 375. 克隆二叉樹(深復(fù)制)

/*** 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;//將左右孩子結(jié)點(diǎn)入隊列，作為下一層的元素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));} };

參考其他思路

之前的構(gòu)造的思路會導(dǎo)致空間嚴(yán)重浪費(fèi)，并且時間耗費(fèi)也較多。
關(guān)于二叉樹是否對稱，我們要比較的是根結(jié)點(diǎn)的左子樹與右子樹是不是相互翻轉(zhuǎn)的。遞歸遍歷的時候要同時遍歷兩棵樹，比較兩棵子樹的里側(cè)和外側(cè)元素是否相同。
本題的遍歷順序?yàn)楹笮虮闅v，因?yàn)橐ㄟ^遞歸函數(shù)的返回值來判斷兩個子樹的內(nèi)測結(jié)點(diǎn)與外側(cè)結(jié)點(diǎn)是否相等。
一棵樹遍歷順序?yàn)樽笥抑?#xff0c;另一棵樹遍歷順序是右左中。這里可以理解為一種回溯的思想。

遞歸法

1、確定遞歸地參數(shù)和返回值
參數(shù)：該結(jié)點(diǎn)的左子樹結(jié)點(diǎn)、右子樹結(jié)點(diǎn)
返回值：bool類型
bool compare(TreeNode* left,TreeNode* right)
2、確定終止條件
1、左右都為空，返回true
2、左右只有一個為空，返回false
3、左右結(jié)點(diǎn)均不為空，比較結(jié)點(diǎn)數(shù)值，不相同返回false
4、左右結(jié)點(diǎn)均不為空，數(shù)值相同返回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、確定單層遞歸邏輯
處理左右結(jié)點(diǎn)皆不為空且數(shù)值相同的情況。
1、比較二叉樹外側(cè)是否對稱：傳入左結(jié)點(diǎn)的左孩子，右結(jié)點(diǎn)的右孩子。
2、比較內(nèi)側(cè)是否對稱，傳入左結(jié)點(diǎn)的右孩子，右結(jié)點(diǎn)的左孩子。
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);} };

迭代法

這一題的本質(zhì)是判斷兩個樹是否相互翻轉(zhuǎn)，并非簡單的遍歷。這里可以使用隊列來比較兩個樹(根結(jié)點(diǎn)的左右子樹)是否相互翻轉(zhuǎn)。

/*** 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); //將左子樹頭結(jié)點(diǎn)加入隊列que.push(root->right); //將右子樹頭結(jié)點(diǎn)加入隊列while(!que.empty()) //判斷兩個樹是否翻轉(zhuǎn){TreeNode* leftNode = que.front();que.pop();TreeNode* rightNode = que.front();que.pop();if(!leftNode && !rightNode) {//左右結(jié)點(diǎn)均為空，說明此時是對稱的continue;}//左右一個結(jié)點(diǎn)不為空，或者都不為空但是數(shù)值不同，返回falseif((!leftNode || !rightNode || (leftNode->val!=rightNode->val))){return false;}//外側(cè)que.push(leftNode->left); //左左que.push(rightNode->right); //右右//內(nèi)側(cè)que.push(leftNode->right);que.push(rightNode->left);}return true;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 101. 对称二叉树 思考分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。