国外建设网站的软件,西宁设计网站建设,网站建设页面,emlog怎么转wordpress今日任务
654.最大二叉树 - Medium617.合并二叉树 - Easy700.二叉搜索树中的搜索 - Easy98.验证二叉搜索树 - Medium 654.最大二叉树 - Medium
题目链接#xff1a;. - 力扣#xff08;LeetCode#xff09; 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法…今日任务
654.最大二叉树 - Medium617.合并二叉树 - Easy700.二叉搜索树中的搜索 - Easy98.验证二叉搜索树 - Medium 654.最大二叉树 - Medium
题目链接. - 力扣LeetCode 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 最大二叉树 。 思路递归法
class Solution {
private:// 在左闭右开区间[left, right)构造二叉树TreeNode* traversal(vectorint nums, int left, int right) {if (left right) return nullptr;// 分割点下标maxValueIndexint maxValueIndex left;for (int i left 1; i right; i) {if (nums[i] nums[maxValueIndex]) maxValueIndex i;}TreeNode* root new TreeNode(nums[maxValueIndex]);// 左闭右开[left, maxValueIndex)root-left traversal(nums, left, maxValueIndex);// 左闭右开[maxValueIndex 1, right)root-right traversal(nums, maxValueIndex 1, right);return root;}
public:TreeNode* constructMaximumBinaryTree(vectorint nums) {return traversal(nums, 0, nums.size());}
};617.合并二叉树 - Easy
题目链接. - 力扣LeetCode 给你两棵二叉树 root1 和 root2 。 想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。 返回合并后的二叉树。 注意: 合并过程必须从两个树的根节点开始。 思路递归法前序遍历同时传入两棵树的节点一起操作
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 NULL) return t2; // 如果t1为空合并之后就应该是t2if (t2 NULL) return t1; // 如果t2为空合并之后就应该是t1// 修改了t1的数值和结构t1-val t2-val; // 中t1-left mergeTrees(t1-left, t2-left); // 左t1-right mergeTrees(t1-right, t2-right); // 右return t1;}
};700.二叉搜索树中的搜索 - Easy
题目链接. - 力扣LeetCode 给定二叉搜索树BST的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null 。 思路二叉搜索树是一个有序树若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树
递归法
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root NULL || root-val val) return root;TreeNode* result NULL;if (root-val val) result searchBST(root-left, val);if (root-val val) result searchBST(root-right, val);return result;}
};迭代法
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root ! NULL) {if (root-val val) root root-left;else if (root-val val) root root-right;else return root;}return NULL;}
};98.验证二叉搜索树 - Medium
题目链接. - 力扣LeetCode 给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 提示 中序遍历二叉搜索树中没有重复元素要比较的是 左子树所有节点小于中间节点右子树所有节点大于中间节点验证二叉搜索树就相当于变成了判断一个序列是不是递增的了
递归法
class Solution {
private:vectorint vec;void traversal(TreeNode* root) {if (root NULL) return;traversal(root-left);vec.push_back(root-val); // 将二叉搜索树转换为有序数组traversal(root-right);}
public:bool isValidBST(TreeNode* root) {vec.clear(); // 不加这句在leetcode上也可以过但最好加上traversal(root);for (int i 1; i vec.size(); i) {// 注意要小于等于搜索树里不能有相同元素if (vec[i] vec[i - 1]) return false;}return true;}
};迭代法
class Solution {
public:bool isValidBST(TreeNode* root) {stackTreeNode* st;TreeNode* cur root;TreeNode* pre NULL; // 记录前一个节点while (cur ! NULL || !st.empty()) {if (cur ! NULL) {st.push(cur);cur cur-left; // 左} else {cur st.top(); // 中st.pop();if (pre ! NULL cur-val pre-val)return false;pre cur; //保存前一个访问的结点cur cur-right; // 右}}return true;}
};今日总结
三四题充分利用二叉搜索树的性质还是比较好解的
