四川建设机械网站,连云港网站关键词优化,什么是域名解析,滨湖网站制作题目#xff1a;最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。 …题目最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。
题解 构造树一般采用的是前序遍历因为先构造中间节点然后递归构造左子树和右子树。 确定递归函数的参数和返回值参数传入的是存放元素的数组返回该数组构造的二叉树的头结点返回类型是指向节点的指针。 确定终止条件题目中说了输入的数组大小一定是大于等于1的所以我们不用考虑小于1的情况那么当递归遍历的时候如果传入的数组大小为1说明遍历到了叶子节点了。那么应该定义一个新的节点并把这个数组的数值赋给新的节点然后返回这个节点。 这表示一个数组大小是1的时候构造了一个新的节点并返回。 确定单层递归的逻辑 先要找到数组中最大的值和对应的下标 最大的值构造根节点下标用来下一步分割数组。最大值所在的下标左区间 构造左子树最大值所在的下标右区间 构造右子树 class Solution {
public:TreeNode* constructMaximumBinaryTree(vectorint nums) {TreeNode* temp_node new TreeNode(0);if(nums.size()1){temp_node-valnums[0];return temp_node;}int maxval0;int maxvalindex0;for(int i0;inums.size();i){if(nums[i]maxval){maxvalnums[i];maxvalindexi;}}temp_node-valmaxval;if(maxvalindex0){vectorint leftvec(nums.begin(),nums.begin()maxvalindex);temp_node-leftconstructMaximumBinaryTree(leftvec);}if(maxvalindex(nums.size()-1)){vectorint rightvec(nums.begin()maxvalindex1,nums.end());temp_node-rightconstructMaximumBinaryTree(rightvec);}return temp_node;}
};注意类似用数组构造二叉树的题目每次分隔尽量不要定义新的数组而是通过下标索引直接在原数组上操作这样可以节约时间和空间上的开销。一般情况来说如果让空节点空指针进入递归就不加if如果不让空节点进入递归就加if限制一下 终止条件也会相应的调整。 TreeNode* searsh(vectorint nums,int left,int right){if(leftright){return nullptr;}int maxvalindexleft;for(int ileft1;iright;i){if(nums[i]nums[maxvalindex])maxvalindexi;}TreeNode* rootnew TreeNode(nums[maxvalindex]);root-leftsearsh(nums,left,maxvalindex);root-rightsearsh(nums,maxvalindex1,right);return root;}题目合并二叉树
给你两棵二叉树 root1 和 root2 。当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。
题解 深度优先搜索可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树并将对应的节点进行合并。两个二叉树的对应节点可能存在以下三种情况对于每种情况使用不同的合并方式。 如果两个二叉树的对应节点都为空则合并后的二叉树的对应节点也为空如果两个二叉树的对应节点只有一个为空则合并后的二叉树的对应节点为其中的非空节点如果两个二叉树的对应节点都不为空则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和此时需要显性合并两个节点。 对一个节点进行合并之后还要对该节点的左右子树分别进行合并。这是一个递归的过程。 class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1nullptr){return root2;}if(root2nullptr){return root1;}auto megednew TreeNode(root1-valroot2-val);meged-leftmergeTrees(root1-left,root2-left);meged-rightmergeTrees(root1-right,root2-right);return meged;}
};时间复杂度O(min(m,n))其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作因此被访问到的节点数不会超过较小的二叉树的节点数。 空间复杂度O(min(m,n))其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数递归调用的层数不会超过较小的二叉树的最大高度最坏情况下二叉树的高度等于节点数。 那么中序遍历也是可以的代码如下 class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 NULL) return t2; // 如果t1为空合并之后就应该是t2if (t2 NULL) return t1; // 如果t2为空合并之后就应该是t1// 修改了t1的数值和结构t1-left mergeTrees(t1-left, t2-left); // 左t1-val t2-val; // 中t1-right mergeTrees(t1-right, t2-right); // 右return t1;}
};后序遍历依然可以代码如下 class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 NULL) return t2; // 如果t1为空合并之后就应该是t2if (t2 NULL) return t1; // 如果t2为空合并之后就应该是t1// 修改了t1的数值和结构t1-left mergeTrees(t1-left, t2-left); // 左t1-right mergeTrees(t1-right, t2-right); // 右t1-val t2-val; // 中return t1;}
};题目二叉搜索树中的搜索
给定二叉搜索树BST的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null 。
题解 二叉搜索树是一个有序树若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树。 一提到二叉树遍历的迭代法可能立刻想起使用栈来模拟深度遍历使用队列来模拟广度遍历。对于二叉搜索树可就不一样了因为二叉搜索树的特殊性也就是节点的有序性可以不使用辅助栈或者队列就可以写出迭代法。对于一般二叉树递归过程中还有回溯的过程例如走一个左方向的分支走到头了那么要调头在走右分支。而对于二叉搜索树不需要回溯的过程因为节点的有序性就帮我们确定了搜索的方向。 class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root!nullptr){if(root-valval){rootroot-left;}else if(root-valval){rootroot-right;}else{return root;}}return nullptr;}
};确定递归函数的参数和返回值,递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点。 确定终止条件如果root为空或者找到这个数值了就返回root节点。 确定单层递归的逻辑如果root-val val搜索左子树如果root-val val就搜索右子树最后如果都没有搜索到就返回NULL。 class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(rootnullptr||root-valval){return root;}if(root-valval){return searchBST(root-left,val);}if(root-valval){return searchBST(root-right,val);}return nullptr;}
};题目验证二叉搜索树
给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
题解 要知道中序遍历下输出的二叉搜索树节点的数值是有序序列。有了这个特性验证二叉搜索树就相当于变成了判断一个序列是不是递增的了。 class Solution {
public:vectorint temp_vec;void trave(TreeNode *root){if(rootnullptr)return;trave(root-left);temp_vec.push_back(root-val);trave(root-right);}bool isValidBST(TreeNode* root) {temp_vec.clear();trave(root);for(int i1;itemp_vec.size();i){if(temp_vec[i]temp_vec[i-1])return false;}return true;}
};可以用迭代法模拟二叉树中序遍历 bool isValidBST(TreeNode* root) {stackTreeNode* st;TreeNode* curroot;TreeNode* prenullptr;while(cur!nullptr||!st.empty()){if(cur!nullptr){st.push(cur);curcur-left;}else{curst.top();st.pop();if(pre!nullptrcur-valpre-val){return false;}precur;curcur-right;}}return true;}
