C++ 判断对称二叉树的递归和非递归做法 [LeetCode 101]
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++ 判断对称二叉树的递归和非递归做法 [LeetCode 101]，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2362字，纯文字阅读大概需要4分钟。
内容图文
题目：
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [
1,2,2,3,4,4,3] 是对称的。
1
/22
/ \ /3443
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/22
\ 33
链接：https://leetcode-cn.com/problems/symmetric-tree
最开始的思路是用层次遍历，每一行看看是不是回文数组，但后来发现例如样例2那样的树就会判断错误，递归也没想好怎么个调用思路。
正确的递归思路：来源：https://leetcode-cn.com/u/haventmetyou-2/
1.怎么判断一棵树是不是对称二叉树？ 答案：如果所给根节点，为空，那么是对称。如果不为空的话，当他的左子树与右子树对称时，他对称
2.那么怎么知道左子树与右子树对不对称呢？在这我直接叫为左树和右树 答案：如果左树的左孩子与右树的右孩子对称，左树的右孩子与右树的左孩子对称，那么这个左树和右树就对称。
仔细读这句话，是不是有点绕？怎么感觉有一个功能A我想实现，但我去实现A的时候又要用到A实现后的功能呢？
当你思考到这里的时候，递归点已经出现了： 递归点：我在尝试判断左树与右树对称的条件时，发现其跟两树的孩子的对称情况有关系。
想到这里，你不必有太多疑问，上手去按思路写代码，函数A（左树，右树）功能是返回是否对称
def 函数A（左树，右树）： 左树节点值等于右树节点值 且 函数A（左树的左子树，右树的右子树），函数A（左树的右子树，右树的左子树）均为真 才返回真
/*
*
* 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) {
return isSame(root,root);
}
bool isSame(TreeNode* q,TreeNode *p)
{
if(q==nullptr&&p==nullptr) returntrue;
elseif(q&&!p||!q&&p) returnfalse;
elseif(q->val==p->val)
{
return isSame(q->left,p->right)&&isSame(q->right,p->left);
}
returnfalse;
}
};
非递归思路与层次遍历类似，只不过改成每次比较当前两结点的最左和最右得结点值是否相等：
/*
*
* 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==nullptr) returntrue;
queue<TreeNode * > vec;
vec.push(root->left);
vec.push(root->right);
while(vec.size()!=0)
{
TreeNode * a=vec.front();
vec.pop();
TreeNode * b=vec.front();
vec.pop();
if(!a&&!b) //两个都是是空则认为为真 {
continue;
}
elseif(a==nullptr||b==nullptr||a->val!=b->val)//有一个不是空或者都不是空而且数值不一样，则为假，直接返回returnfalse;
vec.push(a->left);//这四句代码其实就是递归的顺序
vec.push(b->right);
vec.push(a->right);
vec.push(b->left);
}
returntrue;
}
};
可以发现非递归做法是把递归思路放到循环里了
原文：https://www.cnblogs.com/murenma/p/15337639.html
内容总结
以上是互联网集市为您收集整理的C++ 判断对称二叉树的递归和非递归做法 [LeetCode 101]全部内容，希望文章能够帮你解决C++ 判断对称二叉树的递归和非递归做法 [LeetCode 101]所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。