算法力扣刷題記錄四十二【101. 對稱二叉樹、100.相同的樹、572.另一個樹的子樹】

前言

二叉樹篇，開始對二叉樹操作練習。
記錄四十二【101. 對稱二叉樹】。
繼續。

一、題目閱讀

給你一個二叉樹的根節點 root ， 檢查它是否軸對稱。

示例 1：
在這里插入圖片描述

輸入：root = [1,2,2,3,4,4,3]
輸出：true

示例 2：
在這里插入圖片描述

輸入：root = [1,2,2,null,3,null,3]
輸出：false

提示：

樹中節點數目在范圍 [1, 1000] 內
-100 <= Node.val <= 100

進階：你可以運用遞歸和迭代兩種方法解決這個問題嗎？

二、嘗試實現

思路一

先用遞歸試一下。核心：判斷軸對稱的標準是什么？

遞歸：自己調用自己。暫時沒找到重復的邏輯：

判斷left== right？進入到子樹，不正確。
左子樹走左右中，右子樹走右左中。序列相等？但這是對整個樹。進入到子樹，也不對。

思路二

改變用迭代法。用層序遍歷。
獲得層序結果之后，判斷每一層是偶數且reverse之后相等。但對于示例二，不成立，因為空指針被排除。
思路不成立。

總結：雖然知道要找對稱，但是統一判斷對稱的標準不會。

三、參考思路

參考思路鏈接

學習內容

軸對稱：根節點的左子樹和右子樹是否可以翻轉相等？，如何比較？
從講解獲得正確思路：本次遍歷需要根節點的左子樹和根節點的右子樹同時遍歷。一次性遍歷兩個子樹，才能判斷兩邊節點相不相等。
- 先傳左子樹的left和右子樹的right，此時外側節點判斷相等；
- 再傳左子樹的right和右子樹的left，此時內側節點判斷相等；
- 兩者返回之后，同時都為true，說明對稱。
確定遍歷順序：左右中。處理完左孩子，再處理右孩子，把結果返回給中節點。
嘗試實現中思路不足之處：只處理根節點左子樹，發現根節點右子樹的順序和左邊不一樣。用遍歷順序翻轉，或者如何，都得不到統一的邏輯。

遞歸實現

每一個注釋都是思路。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool iscompare(TreeNode* left,TreeNode* right){ //兩邊同時遍歷，所以兩個參數。返回是否相等，用bool類型。//確定終止條件if(!left && !right) return true;    //同時為空，可以翻轉else if(!left && right) return false; //一個空，一個不為空。肯定不等else if (!right && left) return false;//一個空，一個不為空。肯定不等else if(left->val != right->val) return false;//都不為空，但是值不等//都不為空，值相等。說明可以繼續進行外側比較、內側比較，不用return。bool outside = iscompare(left->left,right->right);  //同時比較，解決了左右遍歷順序不一樣bool inside = iscompare(left->right,right->left);return outside && inside;   //同時返回true。才能返回true}bool isSymmetric(TreeNode* root) {return iscompare(root->left,root->right);}
};

一個樹（左子樹）的遍歷順序是左右中，一個樹（右子樹）的遍歷順序是右左中。

迭代思路1

同時處理根節點左子樹和根節點右子樹。和之前的遍歷不一樣。
用隊列結構：把要比較的兩個節點同時放入隊列中，再同時取出來。判斷取出來的兩個節點能否翻轉。所以如果左右孩子有空，也需要放到隊列里。
用棧結構：還是要同時處理兩個節點。有兩個對象要做比較。 同時放進去，再同時取出來。

迭代實現【隊列結構】

棧結構一樣。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {if(!root) return false;queue<TreeNode*> que;que.push(root->left);//放入左子樹que.push(root->right);//放入右子樹while(!que.empty()){TreeNode* left = que.front(); que.pop();//取出比較對象中的左節點TreeNode* right = que.front();que.pop();//取出比較對象中的右節點if(!left && !right){    //都是空節點continue;}else if(!left || !right || left->val != right->val){return false;}que.push(left->left);que.push(right->right);que.push(left->right);que.push(right->left);}return true;}
};

總結【軸對稱二叉樹】：

依然是遍歷，不同在于：必須同時遍歷兩個子樹。深入任何一個子樹遞歸都是不對的。
比較對象判斷true的條件：同時空；或值相等。其余都是false。
也不可以深入任何一個子樹遞歸遍歷，因為左邊和右邊順序不一樣。
不是層序遍歷。如果非得層序遍歷：得出每一層結果，reverse之后看是否相等。如下（不推薦），上面的解答都很好。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {vector<vector<int>> level;queue<TreeNode*> que;if(!root) return false;que.push(root);while(!que.empty()){int size = que.size();vector<int> vec;while(size--){TreeNode* cur = que.front();que.pop();if(cur){ //不是空節點que.push(cur->left);que.push(cur->right);vec.push_back(cur->val);}else{vec.push_back(INT_MIN);//因為節點的值【-100,100】。用一個最小值代表空。}}level.push_back(vec);}//獲得層序遍歷。包含空。空的數值借助INT_MIN代替。for(int i = 1;i < level.size();i++){vector<int> temp = level[i];reverse(temp.begin(),temp.end());if(temp != level[i]){return false;}}return true;}
};

題目練習

【100.相同的樹】

一、題目

給你兩棵二叉樹的根節點 p 和 q ，編寫一個函數來檢驗這兩棵樹是否相同。

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。

示例 1：

輸入：p = [1,2,3], q = [1,2,3]
輸出：true

示例 2：

輸入：p = [1,2], q = [1,null,2]
輸出：false

示例 3：

輸入：p = [1,2,1], q = [1,1,2]
輸出：false

提示：

兩棵樹上的節點數目都在范圍 [0, 100] 內
-10^4 <= Node.val <= 10^4

思路

判斷兩個樹是否相同。結構相同且值相同。

那么必須同時處理兩個樹，才有比較對象。只對一個樹深入遍歷/做什么操作，都是無用的。
和【101.對稱二叉樹】區別，比較對象。這里比較對象左孩子和左孩子比；右孩子和右孩子比。遞歸調用的參數給對。

代碼實現

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(!p && !q) return true;  //傳入節點同時為空，可以對應else if(!p && q) return false;//一個空，另一個不是空。不可能對應。else if(p && !q) return false;//一個空，另一個不是空。不可能對應。else if(p->val != q->val) return false;//值不等，不可能對應。bool leftchild = isSameTree(p->left,q->left); bool rightchild = isSameTree(p->right,q->right);return leftchild && rightchild;}
};

【572.另一個樹的子樹】

題目

給你兩棵二叉樹 root 和 subRoot 。檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹。如果存在，返回 true ；否則，返回 false 。

二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有后代節點。tree 也可以看做它自身的一棵子樹。

示例 1：

輸入：root = [3,4,5,1,2], subRoot = [4,1,2]
輸出：true

示例 2：

輸入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
輸出：false

提示：

root 樹上的節點數量范圍是 [1, 2000]
subRoot 樹上的節點數量范圍是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4

思路

（1）子樹也是判斷兩個樹相等。可以用【100.題代碼實現】解決相等判斷。
（2）但是得在root中找到等于subRoot根節點值的節點，作為子樹的根節點。用層序遍歷root。

代碼實現

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSame(TreeNode* rootnode,TreeNode* subRootnode){if(!rootnode && !subRootnode) return true;else if(!rootnode && subRootnode) return false;else if(rootnode && !subRootnode) return false;else if(rootnode->val != subRootnode->val) return false;bool leftchild = isSame(rootnode->left,subRootnode->left);bool rightchild = isSame(rootnode->right,subRootnode->right);return leftchild && rightchild;}bool isSubtree(TreeNode* root, TreeNode* subRoot) {//先找到和subRoot值相等的節點，才有可能相等。得遍歷root找到和subRoot值相等的節點，可能作為子樹的根節點//用層序遍歷queue<TreeNode*> que;que.push(root);while(!que.empty()){int size = que.size();while(size--){TreeNode* cur = que.front();que.pop();if(cur->val == subRoot->val){bool subtree = isSame(cur,subRoot);if(subtree) return true;}if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return false;}
};