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

网站开发需要什么关键技术杭州网站建设 双收

网站开发需要什么关键技术,杭州网站建设 双收,泰安网信科技,wordpress 模版位置文章目录 一、题目二、递归法三、迭代法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、递归法 思路分析:这道题目标就是要对比左右两半的树是否对称,因此对比不是左右节点是否相等&…

文章目录

  • 一、题目
  • 二、递归法
  • 三、迭代法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述
在这里插入图片描述

二、递归法

  思路分析:这道题目标就是要对比左右两半的树是否对称,因此对比不是左右节点是否相等,而是根节点的左子树和右子树是否相等。刚开始笔者想到的是做层序遍历,然后判断每层的值是否前后对称,但是由于层序遍历当中空节点是不显示的,因此例二也会判成对称树。为此我们可以把空节点也显示出来,但是这样一来遍历的节点数量要大于等于树本身非空节点的数量,徒增计算量。经过一番思考,还是想用递归法实现。程序当中我们对比两个结点是否相等,一共有四种情况。其实还有一种情况,就是节点1的值等于节点2的值,这部分判断包含在cmpTree函数的递归语句return当中,如果出现第五种情况,最终会以第一种情况的形式返回

  • 1.节点1、节点2为空,对称,返回true;
  • 2.节点1为空、节点2不为空, 不对称,返回false;
  • 3.节点1不为空、节点2为空, 不对称,返回false;
  • 4.节点1不为空、节点2不为空, 但值不相等,不对称,返回false;
      程序如下
class Solution {
public:// 递归法bool cmpTree(TreeNode* node1, TreeNode* node2) {if (node1 == NULL && node2 == NULL) return true;    // 二者均为空节点if (node1 == NULL || node2 == NULL || node1->val != node2->val) return false;   // 其他三种情况return cmpTree(node1->left, node2->right) && cmpTree(node1->right, node2->left);}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return cmpTree(root->left, root->right);}
};

三、迭代法

  思路分析:迭代法使用了队列,先将根节点的左右节点压入队中,然后判断语句的思路和递归当中一致,最后再将要比较的节点按顺序入队,注意节点1的左节点和节点2的右节点比较,节点1的右节点和节点2的左节点比较

class Solution2 {
public:// 迭代法bool isSymmetric(TreeNode* root) {if (!root) return true;     // 根节点为空,直接返回queue<TreeNode*> que;que.push(root->left);que.push(root->right);while (!que.empty()) {TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front();que.pop();if (!node1 && !node2) continue;if (!node1 || !node2 || node1->val != node2->val) return false;que.push(node1->left);que.push(node2->right);que.push(node1->right);que.push(node2->left);}return true;}
};

三、完整代码

# include <iostream>
# include <vector>
# include <queue>
# include <string>
# include <stack>
using namespace std;// 树节点定义
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 cmpTree(TreeNode* node1, TreeNode* node2) {if (node1 == NULL && node2 == NULL) return true;    // 二者均为空节点if (node1 == NULL || node2 == NULL || node1->val != node2->val) return false;   // 其他三种情况return cmpTree(node1->left, node2->right) && cmpTree(node1->right, node2->left);}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return cmpTree(root->left, root->right);}
};class Solution2 {
public:// 迭代法bool isSymmetric(TreeNode* root) {if (!root) return true;     // 根节点为空,直接返回queue<TreeNode*> que;que.push(root->left);que.push(root->right);while (!que.empty()) {TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front();que.pop();if (!node1 && !node2) continue;if (!node1 || !node2 || node1->val != node2->val) return false;que.push(node1->left);que.push(node2->right);que.push(node1->right);que.push(node2->left);}return true;}
};void my_print2(vector<vector<int>>& v, string str) {cout << str << endl;for (vector<vector<int>>::iterator vit = v.begin(); vit < v.end(); ++vit) {for (vector<int>::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}// 前序遍历递归法创建二叉树,每次迭代将容器首元素弹出(弹出代码还可以再优化)
void Tree_Generator(vector<string>& t, TreeNode*& node) {if (t[0] == "NULL" || !t.size()) return;    // 退出条件else {node = new TreeNode(stoi(t[0].c_str()));    // 中t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->left);              // 左t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->right);             // 右}
}vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();  // size必须固定, que.size()是不断变化的vector<int> vec;for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);   // 空节点不入队if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}int main()
{vector<string> t = { "1", "2", "3", "NULL", "NULL", "4", "NULL", "NULL", "2", "4", "NULL", "NULL", "3", "NULL", "NULL" };   // 前序遍历//vector<string> t = { "1", "2", "NULL", "3", "NULL", "NULL", "2", "NULL", "3", "NULL", "NULL" };   // 前序遍历TreeNode* root = new TreeNode();Tree_Generator(t, root);vector<vector<int>> tree = levelOrder(root);my_print2(tree, "目标树:");Solution2 s1;bool result = s1.isSymmetric(root);if (result) cout << "对称树" << endl;else cout << "非对称树" << endl;system("pause");return 0;
}

end

http://www.yayakq.cn/news/196660/

相关文章:

  • 怎么做点图片链接网站网站建设捌金手指下拉三
  • 虚拟主机做多个网站代理app软件
  • 电子商务网站建设与实践上机指导网站设计论文的题目
  • 做网站需要编码吗京津冀协同发展背景
  • 石家庄模板建站微盟小程序商城
  • 浙江省建设门户网站网站建设整改情况
  • 在静安正规的设计公司网站郑州新像素ui设计培训收费
  • 网站推广怎样做网站添加外链
  • html5商业网站开发北大青鸟哈尔滨网站设计公司地址
  • 饿了吗网站做的比较好的地方南城网站建设多少钱
  • 科院公司网站建设目标是什么做视频直播网站需要多少资金
  • 南昌网站设计企业建设通查询
  • 用vue.js做网站jsp网站有哪些
  • 门户网站建设和内容保障工作wordpress登录注册页面模板
  • 怎么用手机制作手机网站ps网站轮播图怎么做
  • 网站建设网页制作软件wordpress竖排主题
  • 自己的网站没有域名解析建设一个电商网站的流程
  • 重庆忠县网站建设宠物网站建设规划书
  • 知名网站建设设计番号网站怎么做
  • 温岭市建设规划局网站WordPress到底好不好用
  • 免费备案域名英文站 wordpress seo优化
  • 北京门户网站制作公司珠海网站建设报价
  • 旅游网网站建设wordpress视频不全屏播放
  • 做网站 怎么做留言php做网站安全性
  • 查公司信息的网站是哪个网站建德网站优化公司
  • 建设一个聊天类的网站可做商业用途的图片网站
  • 建材建设网站邓修明调研成都网站建设
  • 网站推广含义网站设计英文翻译
  • 百色做网站好用的cms系统
  • 网站的注册页面怎么做成都网多多