要加强网站内容的建设,视频网站会员系统怎么做,有哪些做特卖的网站有哪些,网络服务提供者知道或者应当知道网络昨天光写题忘写文章了#xff0c;合并到今天一起写了///一共七个题///
【二叉搜索树中第k小元素】
给定一个二叉搜索树的根节点 root #xff0c;和一个整数 k #xff0c;请你设计一个算法查找其中第 k 个最小元素#xff08;从 1 开始计数#xff09;。
思路#xf…昨天光写题忘写文章了合并到今天一起写了///一共七个题///
【二叉搜索树中第k小元素】
给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 个最小元素从 1 开始计数。
思路
搜索树第一反应肯定是中序升序。方便起见我们先建立一个全局变量用来记录当前访问的节点是第几个然后把中序遍历的板子糊上去就好啦。这题标mid我是不同意的他真的不配。。。
class Solution {
public:int cnt0;int kthSmallest(TreeNode* root, int k) {stackTreeNode* stk;while(root!nullptr||!stk.empty()){while(root!nullptr){stk.push(root);rootroot-left;}root stk.top();stk.pop();if(cntk)break;rootroot-right;}return root-val;}
};
【二叉树右视图】
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。
思路
第一种带计数的层序遍历把每一层的最后一个节点放进答案里面就好了。第二种变形的先序遍历根左右改成根右左记录当前层数这样可以保证第一次遍历到某层的节点的时候访问的必定是当前层最右侧的节点。懒得实现了。。
class Solution {
public:vectorint rightSideView(TreeNode* root) {vectorint ans;queueTreeNode* q;if (root)q.push(root);while (!q.empty()) {int cnt q.size();TreeNode* cur nullptr;while (cnt) {cur q.front();q.pop();if (cur-left)q.push(cur-left);if (cur-right)q.push(cur-right);if (cnt-- 1)ans.push_back(cur-val);}}return ans;}
};
【二叉树展开为链表】
给你二叉树的根结点 root 请你将它展开为一个单链表
展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。
思路
第一种拆树。对任意节点如果没有左子树显然已经符合要求如果有的话把左子树拆下来放右子树那右子树怎么办呢显然右子树会在左子树全部遍历完以后才被遍历所以我们暂时把它接到左子树最右下角的节点右边等着后面再去处理。如此一路向右下行拆完所有节点的时候就完成了。第二种既然要的是先序遍历顺序的链表那我们先序遍历一遍然后把每个当前节点都拆下来重装一遍行不行答案是不行......按照先序拆下来的话处理完根节点孩子都找不到了还怎么遍历......但是我们可以倒着来啊如果我们对每一个节点都先处理完它的孩子再处理它自己那么孩子节点丢了就丢了呗反正再也用不着了啊。于是我们建立一个pre指针指向当前节点之前最后被处理的那个节点并把当前节点接在pre的前面然后成为新的pre就解决问题啦。当然因为是倒着接的所以遍历顺序得改成“右左根”这样递归嘛改顺序太简单了换一下代码顺序就好啦。
class Solution {
public:void flatten(TreeNode* root) {while(root){if(root-left!nullptr) {TreeNode* Rroot-left;while(R-right) RR-right;R-rightroot-right;root-rightroot-left;root-leftnullptr;}rootroot-right;}return;}
};class Solution {
public:TreeNode* pre nullptr;void flatten(TreeNode* root) {
//先序遍历倒序右左根if(rootnullptr)return;flatten(root-right);flatten(root-left);root-rightpre;root-leftnullptr;preroot;}
};
【从前序与中序遍历序列构造二叉树】
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
思路
这题虽然写了双解但栈迭代那个我只能说我看懂了会写代码了...要我写题解思路实在是做不到就写一下递归的思路算了qaq。
其实这个构造二叉树的过程用自然语言描述非常简单我们最后做的不过是用代码翻译了这个过程用前序找到当前的根节点在中序找到根节点的位置此时我们知道了左右子树各自的节点数量which means我们知道了前序和中序序列中哪一段属于左子树哪一段属于右子树此时已经可以递归算好参数传一下就搞定啦。不过这个参数看起来真的蛮恶心的
class Solution {
public:TreeNode* helper(vectorint preorder, vectorint inorder, int l1,int r1, int l2, int r2) {//区间不合法退出递归if (l1 r1 || l2 r2)return nullptr;//取先序首位int curVal preorder[l1];//在中序找到int i l2;for (; i r2; i) {if (inorder[i] curVal)break;}//构建根节点TreeNode* root new TreeNode(curVal);//确定左子树节点数更新左子树区间递归构建root-left helper(preorder, inorder, l1 1, i l1 - l2, l2, i - 1);//右子树同理root-right helper(preorder, inorder, i l1 - l2 1, r1, i 1, r2);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int s1 preorder.size();int s2 inorder.size();return helper(preorder, inorder, 0, s1 - 1, 0, s2 - 1);}
};
【路径总和】
给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。
思路
这题也写了双解从两个解都获得了一点思路的突破可开心了。
双递归对任意节点来说从它出发的满足要求的路径数量往左子树走时的满足路径数量往右子树走时的满足路径数量不走时满足路径数量。而左右子树的满足路径数量又可以用同样的方式获得于是第一个递归建立了它返回了每个节点作为起点时可以提供的路径数量。然后我们建立第二个递归去遍历所有节点并加和它们提供的路径数量最后返回总数。前缀和为了优化双递归中大量重复的计算我们试着来建立一个表记录根节点到当前节点的路径和。然后就可以用“子数组和”的思想在树的遍历过程中记录满足数量啦虽然底层逻辑是一样的但是把这个方法应用到树上的时候有一个很重要的不同点数组的遍历只会从前往后走可是树的遍历是有倒退过程的诶所以当我们用完某个节点并退出这颗子树的时候必须要把当前节点提供的路径和从表中删去因为剩余还未遍历的路径都不可能再经过这个节点啦那么即使它提供的前缀和在“数值”上满足了题目的要求实际上相应的路径确是不存在的
class Solution {
public:int cal(TreeNode* root, long long target) {if (root nullptr)return 0;return cal(root-left,target-root-val)cal(root-right,target-root-val)(root-valtarget);}int pathSum(TreeNode* root, long long targetSum) {if (root nullptr)return 0;int ans 0;ans cal(root, targetSum);ans pathSum(root-left, targetSum);ans pathSum(root-right, targetSum);return ans;}
};
class Solution {
private:unordered_maplong long, int prefixMap;long long target;public:int pathSum(TreeNode* root, long long targetSum) {prefixMap.clear();target targetSum;prefixMap[0] 1;return recur(root, 0);}private:int recur(TreeNode* node, long long curSum) {if (node nullptr) {return 0;}int res 0;curSum node-val;res prefixMap[curSum - target];prefixMap[curSum];res recur(node-left, curSum);res recur(node-right, curSum);prefixMap[curSum]--;return res;}
};【二叉树最近公共祖先】
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
思路
嗯这题我自己先造了一个小屎山qaq虽然很屎但自己写并一次性AC的快乐还是让我决定给这坨答辩留下一点记录。
屎山版用一个表按照中序遍历序列把每个节点出现的次序记下来然后从根节点开始判断当前节点与p和q的位置关系走到p自身或q自身或第一个使得p和q在自身两边的节点时找到答案。消息传递版对任意节点检查它是否为p或q并从叶子节点开始向上传递消息。首先空节点肯定报告nullptr其次自己是p或q时向上报告自身信息。以上两种情况在访问某节点时立刻就可以完成判断而都不满足时不是p不是q不是空节点进入以下三种情况需要根据左右孩子传上来的信息才能判断。第一种左右孩子均报告无效信息那么继续向上报告无效信息nullptr第二种左右孩子均报告了有效信息时找到答案啦第三种左右孩子中有且只有一个报告了有效信息把该信息继续向上传递。
class Solution {
public:int index 0;unordered_mapTreeNode*, int idx;void dfs(TreeNode* root) {if (root nullptr)return;dfs(root-left);idx.emplace(root, index);dfs(root-right);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//建立中序哈希表dfs(root);int RIndex idx[root];int PIndex idx[p];int QIndex idx[q];//当p和q还在当前节点的同一侧时继续循环while ((PIndex RIndex QIndex RIndex) ||(PIndex RIndex QIndex RIndex)) {if (PIndex RIndex QIndex RIndex) {root root-left;RIndex idx[root];}if (PIndex RIndex QIndex RIndex) {root root-right;RIndex idx[root];}}return root;}
};
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootnullptr)return nullptr;if(rootp||rootq)return root;TreeNode* leftlowestCommonAncestor(root-left,p,q);TreeNode* rightlowestCommonAncestor(root-right,p,q);if(leftnullptrrightnullptr)return nullptr;if(leftright)return root;return left? left:right;}
};
【二叉树最大路径和】
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。
思路
又是一个拓宽思路而且可以复用的题。由于本题在每个节点得到的计算结果可能会向左右两边延伸的最大路径和和每个节点需要传给上层函数的结果至多向一边延伸的最大路径和是不一样的苯人想破头了甚至开始试图传pair给上层...套了三层函数终于解决了以后官解告诉我你在每个节点把要算的给算了用个全局变量记一下然后只把需要传递的传上去不就好了吗啊可恶这样真的显得我很傻逼。
总之还是dfs框架空节点向上传0非空节点先计算以自己为顶点时可以获得的最好结果curSum但这个结果是不上传的它只用来更新全局变量maxInsideSum非空节点继续计算需要上传的结果max自己自己左子树传上来的自己右子树传上来的如果大于0就上传如果最好结果都小于0意味着进入本子树对路径和没有任何正面贡献别进来了传个0回去吧走完整棵树全局变量里记录的就是我们想要的最优解。
class Solution {
public:int maxInsideSum INT_MIN;int dfs(TreeNode* root) {if (root nullptr)return 0;int L dfs(root-left);int R dfs(root-right);int curSum L R root-val;maxInsideSum max(curSum, maxInsideSum);int temp max(L, R) root-val;return temp 0 ? temp : 0;}int maxPathSum(TreeNode* root) {dfs(root);return maxInsideSum;}
};
