class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue q;
if(root == nullptr)return true;
if(root->left == nullptr && root->right == nullptr)return true;
if(root->left == nullptr || root->right == nullptr)return false;
if(root->left->val != root->right->val)return false;
q.push(root->left);
q.push(root->right);
while(!q.empty()){
int size = q.size();
stack stk;
//左半边入栈
for(int i = 0; i < size / 2; i++){
root = q.front();
q.pop();
stk.push(root->left);
stk.push(root->right);
if(root->left)q.push(root->left);
if(root->right)q.push(root->right);
}
//右半边判断
for(int i = 0; i < size / 2; i++){
root = q.front();
q.pop();
if(root->left != stk.top())return false;
stk.pop();
if(root->right != stk.top())return false;
stk.pop();
if(root->left)q.push(root->left);
if(root->right)q.push(root->right);
}
}
return true;
}
};
上边这个由于入栈的时候是可能null入栈的，那你直接拿访问值，这时候会空指针访问出错！
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue q;
if(root == nullptr)return true;
if(root->left == nullptr && root->right == nullptr)return true;
if(root->left == nullptr || root->right == nullptr)return false;
if(root->left->val != root->right->val)return false;
q.push(root->left);
q.push(root->right);
while(!q.empty()){
int size = q.size();
stack stk;
//左半边入栈
for(int i = 0; i < size / 2; i++){
root = q.front();
q.pop();
stk.push(root->left);
stk.push(root->right);
if(root->left)q.push(root->left);
if(root->right)q.push(root->right);
}
//右半边判断
for(int i = 0; i < size / 2; i++){
root = q.front();
q.pop();
if(!((root->left == nullptr && stk.top() == nullptr) || (root->left->val == stk.top()->val)))return false;
stk.pop();
if(!((root->right == nullptr && stk.top() == nullptr) || (root->right->val == stk.top()->val)))return false;
stk.pop();
if(root->left)q.push(root->left);
if(root->right)q.push(root->right);
}
}
return true;
}
};
紧接着上面这个答案加了一个如果是空等于空也是可以的。
但是这里还是忽略了一点，有一个为空一个不为空的时候你也会出现空指针的访问！
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue q;
if(root == nullptr)return true;
if(root->left == nullptr && root->right == nullptr)return true;
if(root->left == nullptr || root->right == nullptr)return false;
if(root->left->val != root->right->val)return false;
q.push(root->left);
q.push(root->right);
while(!q.empty()){
int size = q.size();
stack stk;
//左半边入栈
for(int i = 0; i < size / 2; i++){
root = q.front();
q.pop();
stk.push(root->left);
stk.push(root->right);
if(root->left)q.push(root->left);
if(root->right)q.push(root->right);
}
//右半边判断
for(int i = 0; i < size / 2; i++){
root = q.front();
q.pop();
if((root->left == nullptr && stk.top() != nullptr) || (root->left != nullptr && stk.top() == nullptr))return false;
if(!((root->left == nullptr && stk.top() == nullptr) || (root->left->val == stk.top()->val)))return false;
stk.pop();
if((root->right == nullptr && stk.top() != nullptr) || (root->right != nullptr && stk.top() == nullptr))return false;
if(!((root->right == nullptr && stk.top() == nullptr) || (root->right->val == stk.top()->val)))return false;
stk.pop();
if(root->left)q.push(root->left);
if(root->right)q.push(root->right);
}
}
return true;
}
};
又加了一波判断防护，整出来了！
另外说一下这个解法的整体思路：虽然实现是比较麻烦的，但是思路是值得回顾与总结的。
本道题的关键就是判断对称，对称一定意义上就是玩相等的判断，这时候就想到了一个东西：栈。你先把一半的元素入栈，然后后一半和栈里的元素进行一一比对。由于是树的结构，所以这里采用的就是一层一层去判断的层序遍历的方式。
由于这里对于空指针也要求是对称的，所以你就需要把空指针也入栈了。这个时候你就要注意了，因为空指针一旦入栈，你待会判断相等访问空指针的时候是极容易出错的，也就是第一次答案犯的错误。你这时候就要考虑到，空指针去和空指针去比对的时候，应该是不去访问val直接判断相等与否，而对于空指针和非空去比的时候，直接泥马的return。
同时队列保持和以前一样，实现层序遍历。
那么这道题的遍历的核心逻辑是什么呢？就是遍历当前层，然后判断儿子那一层的对称性。这里有个思维至关重要：就是你遍历当前层的时候，也就是判断下一层的时候，当前层是已经对称的了。因为只有当你的当前一层对称了，你才会去判断下一层是否对称。
另外还有个点：就是对于遍历的那一层的元素，谁的儿子应该入栈，谁的儿子应该判断？按照刚才的思路就是前一半儿子入栈，后一半儿子判断。
那么由于二叉树的当前层已经对称了，也就是说，前一半儿子肯定对应前一半爹。因为当前层的size是层序遍历可以知道的。但是这里又有了一个问题，当你遍历根节点的时候，他只有一个爹啊，两个儿子还是要分成两份的啊。
所以说针对这里上边就单独提前判断，进行处理了一下！
本题也是可以利用递归去实现的，对于递归吧，他和我上边的着手这道题的思维就是不一样的，我想的就是最直接的，树是对称的，树上的所有节点是对称的，也就是去每一层检查节点是否对称就完事了。
但是对于递归的思路，着手点就完全不一样了，他的打开方式就是，判断一个树是否对称，那么把树先给抽象出来，一个根节点和左右子树！！！！！！！！！！！！！！！！
这里的这个抽象非常重要，这里也是二叉树绝大多数递归能写出来的先决条件，这也是二叉树的优势与特点所在。
上面就把问题变成了两个子树的事了。你一个根节点是绝对对称的，那你要整个树对称，只需要保证你的左数和右树是对称的。那么继续往下思考：啥叫左树和右数对称，那不就是左树的左孩子和右树的右孩子对称及左树的右孩子和右树的左孩子对称。好，这个时候就是实现功能A又用到了功能A。
这里的功能A就是判断一个子树和另一个子树是否是对称的！注意这里是两个子树之间是不是对称的，不是子树自己！！
多说一点就是：你要实现的功能A并不一定是这个题目要实现的功能。
这里就是在实现题目过程中，去思考要功能A，然后就出来递归了。
这种递归就是常见的封装一个函数，然后这个函数递归，并不是这道题的函数直接拿着递归。
class Solution {
public:
bool a(TreeNode* leftT, TreeNode* rightT){
if(leftT == nullptr && rightT == nullptr)return true;
if((leftT == nullptr && rightT != nullptr)||(leftT != nullptr && rightT == nullptr)){
return false;
}
if(leftT->val != rightT->val)return false;
return a(leftT->left, rightT->right) && a(leftT->right, rightT->left);
}
bool isSymmetric(TreeNode* root) {
if(root == nullptr)return true;
return a(root->left, root->right);
}
};
对于递归可以仔细去看一下代码随想录的递归三部曲，就在该题讲的：
确定返回类型及参数，确定递归基，单层递归逻辑。
这里是个尾递归，可以整成迭代，整的方式就是你把递归的思路理解，然后用迭代代码去实现。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
stack st; // 这里改成了栈
st.push(root->left);
st.push(root->right);
while (!st.empty()) {
TreeNode* leftNode = st.top(); st.pop();
TreeNode* rightNode = st.top(); st.pop();
if (!leftNode && !rightNode) {
continue;
}
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
st.push(leftNode->left);
st.push(rightNode->right);
st.push(leftNode->right);
st.push(rightNode->left);
}
return true;
}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
stack stk;
if(root == nullptr)return true;
stk.push(root->left);
stk.push(root->right);
while(!stk.empty()){
TreeNode* rightNode = stk.top(); stk.pop();
TreeNode* leftNode = stk.top(); stk.pop();
if(rightNode == nullptr && leftNode == nullptr)continue;
if((rightNode == nullptr && leftNode != nullptr) || (rightNode != nullptr && leftNode == nullptr))return false;
if(rightNode->val != leftNode->val)return false;
stk.push(rightNode->right);
stk.push(leftNode->left);
stk.push(rightNode->left);
stk.push(leftNode->right);
}
return true;
}
};我的版本
还是要说一点：就是对于下面的push其实要求并不是很严格。因为你只要保证他是两对且是一个节点的左对应另一个节点的右就可以了。因为他取得时候始终是成对拿出来的。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
queue 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;
}
// 左右一个节点不为空，或者都不为空但数值不相同，返回false
if ((!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;
}
};
另外上边这个是用队列写出来的，他就是和上边用栈和递归的思路是一样的，但访问的顺序是不一样的。这个说实话就有点类似于层序遍历了。
但是这个入手的思路和递归是一样的，和层序遍历我最开始写的那个是大相径庭的。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）