代码随想录训练营第二十二天| 101.对称二叉树 100.相同的树

101.对称二叉树：

文档讲解：代码随想录|101.对称二叉树

视频讲解：新学期要从学习二叉树开始！ | LeetCode：101. 对称二叉树_哔哩哔哩_bilibili

状态：已做出

思路：

这道题目我初始做的时候想着使用层序遍历来解决这个问题，但是后续做的时候发现出现很多问题，最重要的问题就是如果使用常规的层序遍历，那么队列里没有存储空指针，这样会导致后续遍历判断的时候出现错位，判断出错。后面看了文档的解法，原来使用队列的放书也不是层序遍历，文档给出了三种解法，一个递归，一个队列，一个栈，我就实现了递归和队列的方法，其实思想统一都是把树分为外侧和内测两边，每一边都进行遍历判断，递归就是遍历判断左边节点的左子树和右边节点的右子树，左边阶段的右子树和右边节点的左子树判断，这样深度遍历就可以实现内侧和内侧的遍历，外侧和外侧的遍历，队列就是每次让左边节点的左子树和右边节点的右子树一起入队，左边节点的右子树和右边节点的左子树一起入队，每次循环取出队列里的两个节点进行判断，出错有情况:两个判断的节点一个为空一个不为空，两个都非空但val值不为空。每次递归或者队列循环判断这些情况，最后都不符合上面的情况，那么说明这个数是对称的。

代码如下：

递归：

/*** 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 dfs(TreeNode* left, TreeNode* right) {if(!left && right) return false;//一个为空一个不为空说明不是对称，直接返回falseelse if(left && !right) return false;//一个为空一个不为空不是对称树，返回falseelse if(left && right && (left->val!=right->val)) return false;//两个不为空并且val值不相等说明不对称else if(!left && !right) return true;//两个都是空则是对称，返回true，没有子树所以没有必要进行以下的操作//这里不需要判断左右子树非空且val值也相等的情况，这种情况下不能返回true，要继续对这个节点的左右子树继续进行判断//下面设置两个遍历本别对左子树和右子树外侧和内测进行判断bool a1=dfs(left->left,right->right);//这个是对外侧的子树进行判断是否相等bool a2=dfs(left->right,right->left);//这个是对内测的子树进行判断是否相等return a1 && a2;//当左右子树都相等时才返回true}bool isSymmetric(TreeNode* root) {if(!root) return true;return dfs(root->left,root->right);}
};

队列迭代：

/*** 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 true;queue<TreeNode*>qu;//直接将根节点的左右子树一起放入队列中，后序入队都是成对插入，才能正确的外外、内内判断qu.push(root->left);qu.push(root->right);while(!qu.empty()) {//这里每次同时取出队列里的两个元素，都是成对取数TreeNode* left=qu.front();qu.pop();TreeNode* right=qu.front();qu.pop();if(!left && !right) continue;//当取出的两个节点都时空时，因为没有子树，所以没有必要进行下面的操作，直接continue/**这段代码把所有false的情况都包含了，因为上面的if如果条件是假，那么这两个节点至少有* 一个节点是非空的，那么我的条件是只要判断出一个节点是空整个节点就都是真，直接返回* false，如果两个都是非空，那么最后就判断这两个节点的val值是否相等了*/if((!left || !right || (left->val!=right->val))) return false;//最后把这个两个节点的左右子树对称的放入队列中，下面的插入顺序不能换，因为入队都是成对的qu.push(left->left);qu.push(right->right);qu.push(left->right);qu.push(right->left);}return true;}
};

遇到的困难：

这倒题目虽然是简单的题目，但是如果没使用好方法机会变得很难，当时我一股脑使用层序遍历就出现了很多问题，使用层序遍历没有考虑到会错位的情况。这道题目最简便的方式就是使用文档说的思想，把树分为内侧和外侧，把内侧和外侧分别进行判断，层序遍历要使用应该要把空给考虑进去。

收获：

通过这道题目的练习，学习到了这类题目的优解，没想到要使用内外侧思想来判断，这样思考之后这倒题目竟然一下简单很多，果然思想很重要啊。

100. 相同的树：

状态：已做出

思路：

这道题目可以把两棵树的根结点同时连在一个节点里，合并两棵树，这样结合题目意思就可以看出可以使用上一道题目的思路来解决了。不对合并后的整体树结合题意并不是单纯的判断是否对称，而是判断合并后的树的左右子树是否完全相同，那么我们需要改变判断对象，思路是一样的，把合并的树借节点看成内侧和外侧两种情况，判断对称是内侧和内侧判断，外侧和外侧判断，那么判断树相等则反过来外侧和内侧判断就行了。
代码如下（队列迭代）：

/*** 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) {queue<TreeNode*>qu;//直接将这两树的根节点依次插入到队列里qu.push(p);qu.push(q);while(!qu.empty()) {TreeNode* left=qu.front();qu.pop();TreeNode* right=qu.front();qu.pop();if(!left && !right) continue;if(!left || !right || (left->val!=right->val)) return false;//上面的代码和上一道题目一模一样，就是下面的入对顺序不一样，因为要内测子树和外侧子子树成对，外侧子树和内侧子树成对qu.push(left->left);qu.push(right->left);qu.push(left->right);qu.push(right->right);}return true;}
};