提供建立网站服务的公司,适合个人做的网站有哪些东西吗,.net 微信网站开发,wordpress轮播图替换目录
8.11二叉树展开为链表#xff08;中等#xff09;
8.12从前序与中序遍历序列构造二叉树#xff08;中等#xff09;
8.13路径总和III#xff08;中等#xff09;
8.14二叉树的最近公共祖先#xff08;中等#xff09;
8.15二叉树中的最大路径和#xff08;困…
目录
8.11二叉树展开为链表中等
8.12从前序与中序遍历序列构造二叉树中等
8.13路径总和III中等
8.14二叉树的最近公共祖先中等
8.15二叉树中的最大路径和困难 8.11二叉树展开为链表中等
题目描述leetcode链接 114. 二叉树展开为链表 给你二叉树的根结点 root 请你将它展开为一个单链表 展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。 示例 1 输入root [1,2,5,3,4,null,6]
输出[1,null,2,null,3,null,4,null,5,null,6]示例 2 输入root []
输出[]示例 3 输入root [0]
输出[0] 思路 1.将左、右子树分别变为链表L和R
2.根节点的右节点变为L的根节点根节点的左节点为空
3.L尾节点的右节点变为R的根节点
举例说明
见上图
代码
class Solution {
public:void flatten(TreeNode* root) {if (!root) return;flatten(root - left);flatten(root - right);TreeNode* temp root - right;root - right root - left;root - left nullptr;while(root - right) root root - right;root - right temp;}
};
8.12从前序与中序遍历序列构造二叉树中等
题目描述leetcode链接 105. 从前序与中序遍历序列构造二叉树 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]示例 2: 输入: preorder [-1], inorder [-1]
输出: [-1] 思路 1.由于前序遍历的顺序是【根-左子树-右子树】中序遍历的顺序是【左子树-根-右子树】所以由上图的前序遍历preorder可知它的第一个元素3为根节点。那么由中序遍历inorder可知根节点3的左侧元素为左子树共1个元素根节点3的右侧元素为右子树共3个元素。
2.记录3的左子树的前序遍历顺序和中序遍历顺序其中9即为3的左节点
记录3的右子树的前序遍历顺序和中序遍历顺序其中20即为3的右节点
3.记录20的左子树的前序遍历顺序和中序遍历顺序其中15即为20的左节点
记录20的右子树的前序遍历顺序和中序遍历顺序其中7即为20的右节点
举例说明
见上图
代码
class Solution {
public:unordered_mapint, int mp;TreeNode* buildTree(vectorint preorder, vectorint inorder) {int n preorder.size();for (int i 0; i n; i) {mp[inorder[i]] i;}return build(preorder, inorder, 0, n - 1, 0, n - 1);}TreeNode* build(vectorint preorder, vectorint inorder, int pre_l, int pre_r, int in_l, int in_r) {if (pre_l pre_r) return nullptr;//前序遍历中的根节点位置int pre_root pre_l;//中序遍历中的根节点位置int in_root mp[preorder[pre_root]];TreeNode* root new TreeNode(preorder[pre_root]);//左子树节点个数int size_l in_root - in_l;//构造左右子树root - left build(preorder, inorder, pre_root 1, pre_root size_l, in_l, in_root - 1);root - right build(preorder, inorder, pre_root size_l 1, pre_r, in_root 1, in_r);return root;}
};
8.13路径总和III中等
题目描述leetcode链接 437. 路径总和 III 给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。 示例 1 输入root [10,5,-3,3,2,null,11,3,-2,null,1], targetSum 8
输出3
解释和等于 8 的路径有 3 条如图所示。示例 2 输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22
输出3 思路 和560. 和为K的子数组类似使用前缀和哈希表的方式来解决只不过我们现在面对的数据是存储在二叉树里面了
注unordered_maplong, int mp和long sum的类型为long要不然有几个测试用例通过不了
举例说明
无
代码
class Solution {
public:int ans 0;unordered_maplong, int mp;int pathSum(TreeNode* root, int targetSum) {mp[0] 1;dfs(root, targetSum, 0);return ans;}void dfs(TreeNode* root, int targetSum, long sum) {if (!root) return;sum root - val;if (mp.find(sum - targetSum) ! mp.end()) ans mp[sum - targetSum];mp[sum];dfs(root - left, targetSum, sum);dfs(root - right, targetSum, sum);mp[sum]--;}
};
8.14二叉树的最近公共祖先中等
题目描述leetcode链接 236. 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 1 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出3
解释节点5和节点1的最近公共祖先是节点3示例 2 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4
输出5
解释节点5和节点4的最近公共祖先是节点5。因为根据定义最近公共祖先节点可以为节点本身。示例 3 输入root [1,2], p 1, q 2
输出1 思路 按照p、q中一节点是否是另一节点的祖先节点可以分为上图两种情况 。 使用递归分以下几种情况讨论
1.如果当前节点为空或者等于p或者等于q返回当前节点
2.如果当前节点左、右子树均不返回空返回当前节点
3.如果当前节点左子树返回不为空右子树为空返回左子树递归结果
4.如果当前节点右子树返回不为空左子树为空返回右子树递归结果
5.如果当前节点左、右子树均返回空返回空
举例说明 代码
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (!root || root p || root q) {return root;}TreeNode* L lowestCommonAncestor(root - left, p, q);TreeNode* R lowestCommonAncestor(root - right, p, q);if (L R) return root;return L ? L : R;}
};8.15二叉树中的最大路径和困难
题目描述leetcode链接 199. 二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root 返回其 最大路径和 。 示例 1 输入root [1,2,3]
输出6
解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6 示例 2 输入root [-10,9,20,null,null,15,7]
输出42
解释最优路径是 15 - 20 - 7 路径和为 15 20 7 42 思路
1.定义一个函数getNum(TreeNode* root)可以计算root节点的贡献值
贡献值可以理解为以该节点为起点在其子树中寻找一条路径使其路径和最大
对空节点而言getNum(NULL)0
2.以下图为例
根节点-10的路径和ans(-10) -10max(getNum(15), 0)max(getNum(-5), 0)
遍历所有节点其中ans的最大值即为二叉树的最大路径和
举例说明 代码
class Solution {
public:int ans INT_MIN;int maxPathSum(TreeNode* root) {getNum(root);return ans;}int getNum(TreeNode* root){if (!root) return 0;int L max(getNum(root - left), 0);int R max(getNum(root - right), 0);ans max(ans, root - val L R);return root - val max(L, R);}
};
