当前位置: 首页 > news >正文

对称二叉树

递归做法

递归三部曲:停止条件:比较完发现没有子树而且可以判断是否相等;参数:对称的左右节点;返回值:bool,是否对称

class Solution {
public:bool compare(TreeNode* left,TreeNode* right){if(left == NULL && right != NULL)return false;if(right == NULL && left != NULL)return false;if(right == NULL&&left==NULL)return true;//空if(left->val != right->val)return false;bool j1 = compare(left->left,right->right);bool j2 = compare(left->right,right->left);if((j1 == j2) && (j1 == true)){return true;}return false;}bool isSymmetric(TreeNode* root) {if(root == NULL)return true;return compare(root->left,root->right);}

迭代做法

每次入栈两个对称的部分(每次入栈顺序是左右右左),比较栈顶元素:

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == NULL) return true;queue<TreeNode*> 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;}// 左右一个节点不为空,或者都不为空但数值不相同,返回falseif ((!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;}
};
http://www.hskmm.com/?act=detail&tid=15206

相关文章:

  • 一例电动车充电器防反接电路分析
  • isEmpty/isNotEmpty/isNotBlank/isBlank-isAnyEmpty/isNoneEmpty/isAnyBlank/isNoneBlank
  • NetCore+Web客户端实现gRPC实时推送
  • 个人项目-论文查重
  • 个人项目作业
  • 软工第二次作业--王腾
  • 牛客周赛 Round 110 E,F题解
  • 第5章:路由(Routing)与直连交换机(Direct Exchange)
  • 搜索百科(4):OpenSearch — 开源搜索的新选择
  • JAVA的计算方式
  • 安装 elasticsearch-9.1.4 - 集群 和 kibana-9.1.4
  • 反码 原码 补码
  • 线性结构常见应用之栈[基于郝斌课程]
  • 实测对比:权威榜单之公众号排版Top 5(含效果对比与适用建议)
  • go的泛型
  • 原码补码反码
  • lc1034-边界着色
  • 【汽车电子】汽车功能安全标准 ISO 26262
  • ISO 26262的不同安全等级:ASIL-D ASIL-C ASIL-B ASIL-A
  • C#学习1
  • 02020405 EF Core基础05-EF Core反向工程、EF Core和ADO.NET Core的联系、EF Core无法做到的事情
  • 02020406 EF Core基础06-EF Core生成的SQL
  • Gemini-2.5-Flash-Image-Preview 与 GPT-4o 图像生成能力技术差异解析​ - 教程
  • 新学期每日总结(第2天)
  • 在CodeBolcks下wxSmith的C++编程教程——使用菜单和组件
  • 单调队列
  • 软工第一次编程
  • 第二次软工作业
  • 9.23总结
  • 日志|力扣|不同路径|最小路径和|动态规划|Javase|IO|File|Javaweb