算法Day20 | 654.最大二叉树, 617.合并二叉树, 700.二叉搜索树中的搜索, 98.验证二叉搜索树

news/2025/3/19 8:11:06/

Day20

    • 654.最大二叉树
    • 617.合并二叉树
    • 700.二叉搜索树中的搜索
    • 98.验证二叉搜索树

654.最大二叉树

题目链接: 654.最大二叉树
递归终止条件一定要先写出来。 终止条件选好,可以省略很多多余的代码
构造二叉树题目,要用前序遍历。因为先构造中节点,再构造左右节点。

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if (nums.empty()) return nullptr;//终止条件int maxValue = nums[0], maxIndex = 0;for (int i = 0; i < nums.size(); ++i) {nums[i] > maxValue ? maxValue = nums[i], maxIndex = i : int{};}auto root = new TreeNode(maxValue);//中vector<int> left(nums.begin(), nums.begin() + maxIndex);root->left = constructMaximumBinaryTree(left);//左vector<int> right(nums.begin() + maxIndex + 1, nums.end());root->right = constructMaximumBinaryTree(right);//右return root;}
};

std::max_element()算法。当然,本质和上述代码没区别。

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if (nums.empty()) return nullptr;auto maxIter = max_element(nums.begin(), nums.end());auto root = new TreeNode(*maxIter);vector<int> left(nums.begin(), maxIter);root->left = constructMaximumBinaryTree(left);vector<int> right(maxIter + 1, nums.end());root->right = constructMaximumBinaryTree(right);return root;}
};

上述两部分代码有点消耗资源,每次递归都要重新构建新的数组。可以将递归函数形参改为数组下标,既只对初始数组进行修改。

class Solution {
public:TreeNode* recursion(vector<int>& nums, int startIndex, int endIndex) {if (endIndex == startIndex) return nullptr;//终止条件int maxValue = nums[startIndex], maxIndex = startIndex;for (int i = startIndex; i < endIndex; ++i) {nums[i] > maxValue ? maxValue = nums[i], maxIndex = i : int{};}auto cur = new TreeNode(maxValue);cur->left = recursion(nums, startIndex, maxIndex);cur->right = recursion(nums, maxIndex + 1, endIndex);return cur;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return recursion(nums, 0, nums.size());}
};

617.合并二叉树

题目链接: 617.合并二叉树
终止条件的选择,可以减少判断
递归

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (!root1) return root2;if (!root2) return root1;auto root = new TreeNode(root1->val + root2->val);root->left = mergeTrees(root1->left, root2->left);root->right = mergeTrees(root1->right, root2->right);return root;}
};
if (!root1) return root2;
if (!root2) return root1;if (!root1 && !root2) return nullptr;

前两条if判断,比第三条if判断范围更广。

上述代码,需要重新构建一个新的节点。可以将原有节点最为新的节点来使用。
递归

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (!root1) return root2;if (!root2) return root1;root1->val += root2->val;root1->left = mergeTrees(root1->left, root2->left);root1->right = mergeTrees(root1->right, root2->right);return root1;}
};

迭代 层序遍历

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (!root1) return root2;if (!root2) return root1;queue<TreeNode*> que;que.push(root1);que.push(root2);while (!que.empty()) {auto cur1 = que.front();que.pop();auto cur2 = que.front();que.pop();cur1->val += cur2->val;if (cur1->left && cur2->left) {que.push(cur1->left);que.push(cur2->left);}if (cur1->right && cur2->right) {que.push(cur1->right);que.push(cur2->right);}if (!cur1->left && cur2->left) cur1->left = cur2->left;if (!cur1->right && cur2->right) cur1->right = cur2->right;}return root1;}
};

700.二叉搜索树中的搜索

题目链接: 700.二叉搜索树中的搜索
递归

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (!root || root->val == val) return root;return val < root->val ? searchBST(root->left, val) :searchBST(root->right, val);}
};

迭代

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root && root->val != val) {root = root->val > val ? root->left : root->right;}return root;}
};

上述两部分代码,有一个隐形操作,if(!root) return nullptr 改成 if(!root) return root


98.验证二叉搜索树

题目链接: 98.验证二叉搜索树
如果是深度遍历,先确定是前中后序遍历哪一个。搜索二叉树,用中序遍历做。

class Solution {
public:long maxValue = LONG_MIN;//按题目要求可得bool isValidBST(TreeNode* root) {if (!root) return true;bool left = isValidBST(root->left);if (root->val > maxValue) {maxValue = root->val;} else return false;bool right = isValidBST(root->right);return left && right;}
};

下述代码不用根据题意来设置最小值。不用是面向测试的编程 😃

class Solution {
public:TreeNode* pre = nullptr; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if (!root) return true;bool left = isValidBST(root->left);if (pre && pre->val >= root->val) return false;pre = root; // 记录前一个节点bool right = isValidBST(root->right);return left && right;}
};

http://www.ppmy.cn/news/103654.html

相关文章

Slower使用教程完整版本【2023年更新】

Slower软件的版本&#xff0c;目前市面上有多种。 如果你指的是Slower器加速软件的话&#xff0c;可以看下面的教程&#xff1a; Slower是一款很不错的安全国际互联网工具&#xff0c;广泛用于外贸与留学生行业&#xff0c;设计师行业与科研行业。但是&#xff0c;因为使用过…

【业务功能篇05】Springboot+MybatisPuls 分页查询设计

业务场景: 针对一个问题表单进行筛选,查询过滤后的数据,是一个基本的功能,而随着数据过多,前端表格设计时是需要有一个分页的功能,比如查询了有100条,那么我们设定一页10条,分成10页给业务看,那么这里后端接口就需要返回哪些东西: 问题总数量,当前分页,页大小,以…

30:透彻了解inlining的里里外外

编译器最优化机制通常被设计用来浓缩那些“不含函数调用”的代码&#xff0c;所以当你inline某个函数&#xff0c;或许编译器就因此有能力对它&#xff08;函数本体&#xff09;执行语境相关最优化。 然而inline函数也有使用的代价。 inline函数背后的整体观念是&#xff0c;…

高精度电压源如何设计出来的

高精度电压源是一种用于提供高精度电压的电子设备&#xff0c;通常用于测量和控制系统。高精度电压源的设计是一个复杂的过程&#xff0c;需要考虑多个因素&#xff0c;包括电路设计、元件选型、测量误差、稳定性等。下面将从电路设计和元件选型两个方面&#xff0c;详细介绍高…

【大数据之Hive】三、Linux下安装MySQL8.0.33

1 安装MySQL &#xff08;1&#xff09;解压MySQL安装包: tar -xf mysql-8.0.33-1.el7.x86_64.rpm-bundle.tar -C /opt/module/mysql&#xff08;2&#xff09;卸载系统自带的mariadb&#xff1a; sudo rpm -qa | grep mariadb | xargs sudorpm -e --nodeps&#xff08;3&am…

自学web前端能找到工作吗?是否有必要参加前端培训?

是的&#xff0c;自学前端可以帮助您找到工作&#xff0c;参加培训是根据个人学习能力和经济实力来自己决定的。前端开发是一个相对容易入门的领域&#xff0c;并且许多人通过自学成功地找到了前端开发的工作。以下是好程序员的一些建议&#xff0c;可以帮助您在自学前端时提高…

JVM学习(十二):执行引擎

目录 一、执行引擎概述 二、执行引擎的工作过程 三、Java代码编译和执行 3.1 过程概述 3.1 javac前端编译 3.2 Java字节码的执行 3.3 编译和解释概述 3.4 高级语言理解与执行过程&#xff08;机器码、指令、汇编&#xff09; 3.4.1 机器码 3.4.2 指令 3.4.3 指…

【C++】类与对象——六个默认成员函数、构造函数的概念和特征,析构函数的概念和特征

文章目录 1.类的六个默认成员函数2.构造函数2.1构造函数的概念2.2构造函数的特性 3.析构函数3.1析构函数的概念3.2析构函数的特征 1.类的六个默认成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。   空类中真的什么都没有吗&#xff1f; 并不是&#xff0c;任何…