【leetcode100-044到050】【二叉树】七题合集

2024-01-22 10:04

本文主要是介绍【leetcode100-044到050】【二叉树】七题合集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

昨天光写题忘写文章了,合并到今天一起写了///一共七个题///

【二叉搜索树中第k小元素】

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

思路:

搜索树!第一反应肯定是中序升序。方便起见我们先建立一个全局变量用来记录当前访问的节点是第几个,然后把中序遍历的板子糊上去就好啦。这题标mid我是不同意的,他真的不配。。。

class Solution {
public:int cnt=0;int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> stk;while(root!=nullptr||!stk.empty()){while(root!=nullptr){stk.push(root);root=root->left;}root =stk.top();stk.pop();if(++cnt==k)break;root=root->right;}return root->val;}
};

【二叉树右视图】

给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

思路:

  • 第一种,带计数的层序遍历,把每一层的最后一个节点放进答案里面就好了。
  • 第二种,变形的先序遍历,根左右改成根右左+记录当前层数,这样可以保证第一次遍历到某层的节点的时候访问的必定是当前层最右侧的节点。(懒得实现了。。)
class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> ans;queue<TreeNode*> 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* R=root->left;while(R->right) R=R->right;R->right=root->right;root->right=root->left;root->left=nullptr;}root=root->right;}return;}
};
class Solution {
public:TreeNode* pre= nullptr;void flatten(TreeNode* root) {
//先序遍历倒序:右左根if(root==nullptr)return;flatten(root->right);flatten(root->left);root->right=pre;root->left=nullptr;pre=root;}
};

【从前序与中序遍历序列构造二叉树】

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

思路:

这题虽然写了双解,但栈迭代那个我只能说我看懂了会写代码了...要我写题解思路实在是做不到,就写一下递归的思路算了qaq。

其实这个构造二叉树的过程用自然语言描述非常简单,我们最后做的不过是用代码翻译了这个过程:用前序找到当前的根节点,在中序找到根节点的位置,此时我们知道了左右子树各自的节点数量,which means我们知道了前序和中序序列中哪一段属于左子树,哪一段属于右子树,此时已经可以递归,算好参数传一下就搞定啦。(不过这个参数看起来真的蛮恶心的)

class Solution {
public:TreeNode* helper(vector<int>& preorder, vector<int>& 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(vector<int>& preorder, vector<int>& 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->val==target);}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_map<long 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_map<TreeNode*, 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(root==nullptr)return nullptr;if(root==p||root==q)return root;TreeNode* left=lowestCommonAncestor(root->left,p,q);TreeNode* right=lowestCommonAncestor(root->right,p,q);if(left==nullptr&&right==nullptr)return nullptr;if(left&&right)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;}
};

这篇关于【leetcode100-044到050】【二叉树】七题合集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/632639

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

EasyPlayer.js网页H5 Web js播放器能力合集

最近遇到一个需求,要求做一款播放器,发现能力上跟EasyPlayer.js基本一致,满足要求: 需求 功性能 分类 需求描述 功能 预览 分屏模式 单分屏(单屏/全屏) 多分屏(2*2) 多分屏(3*3) 多分屏(4*4) 播放控制 播放(单个或全部) 暂停(暂停时展示最后一帧画面) 停止(单个或全部) 声音控制(开关/音量调节) 主辅码流切换 辅助功能 屏

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

C++语法知识点合集:11.模板

文章目录 一、非类型模板参数1.非类型模板参数的基本形式2.指针作为非类型模板参数3.引用作为非类型模板参数4.非类型模板参数的限制和陷阱:5.几个问题 二、模板的特化1.概念2.函数模板特化3.类模板特化(1)全特化(2)偏特化(3)类模板特化应用示例 三、模板分离编译1.概念2.模板的分离编译 模版总结 一、非类型模板参数 模板参数分类类型形参与非类型形参 非类型模板

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

Linux性能分析工具合集

Linux性能分析工具合集 工具合集主要包含以下各种工具,对于了解Linux系统结构、网络结构、内核层次具有一定的帮助。 Linux Performance Observability ToolsLinux Static Performance ToolsLinux Performance Benchmark ToolsLinux Performance Tuning ToolsLinux

在二叉树中找到两个节点的最近公共祖先(基于Java)

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo

数据结构--二叉树(C语言实现,超详细!!!)

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树(Binary Tree)是数据结构中一种非常重要的树形结构,它的特点是每个节点最多有两个子节点,通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具

JVM合集

序言: 1.什么是JVM? JVM就是将javac编译后的.class字节码文件翻译为操作系统能执行的机器指令翻译过程: 前端编译:生成.class文件就是前端编译后端编译:通过jvm解释(或即时编译或AOT)执行.class文件时跨平台的,jvm并不是跨平台的通过javap进行反编译 2.java文件是怎么变成.class文件的? 属于前端编译 3..class文件解读 采用1

C语言程序与设计第四版课后习题 - 1~8章大合集

前言 本文章是一个大合集,按照课后习题的命名方式命名,方便寻找,只需要在目录上点相对应的题号即可在这里插入图片描述 第一章课后习题 1.1 编写一个C程序 题目概述: 请参照本章例题,编写一个C程序,输出一下信息: *****************************Very good!***************************** 代码实现: #define