网站开发端突泉建设局三务公开网站

当前位置： 首页 > news >正文

网站开发端,突泉建设局三务公开网站,最美情侣免费视频,体育西网站开发方案530.二叉搜索树的最小绝对差 力扣题目链接 (opens new window) 给你一棵所有节点为非负值的二叉搜索树#xff0c;请你计算树中任意两节点的差的绝对值的最小值。 示例#xff1a; 提示#xff1a;树中至少有 2 个节点。 二叉搜索树是一颗有序的树#xff0c;可以通过中…530.二叉搜索树的最小绝对差 力扣题目链接 (opens new window) 给你一棵所有节点为非负值的二叉搜索树请你计算树中任意两节点的差的绝对值的最小值。 示例 提示树中至少有 2 个节点。 二叉搜索树是一颗有序的树可以通过中序遍历成一个递增的数组再作差;或者遍历过程记录一下前一个节点直接作差。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public://数组版vectorintvec;void traversal(TreeNode root){if(rootnullptr)return;traversal(root-left);vec.push_back(root-val);traversal(root-right);return;}int getMinimumDifference(TreeNode* root) {vec.clear();traversal(root);int mindffINT_MAX;for(int i1;ivec.size();i){if(mindffabs(vec[i]-vec[i-1])){mindffabs(vec[i]-vec[i-1]);}}return mindff;} }; /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public://二叉树版记录前节点TreeNode prenullptr;int result INT_MAX;void traversal(TreeNode* root){if(rootnullptr)return;traversal(root-left);if(pre!nullptr){resultmin(result,root-val-pre-val);}preroot;traversal(root-right);return;}int getMinimumDifference(TreeNode* root) {traversal(root); return result;} }; 501.二叉搜索树中的众数 力扣题目链接 (opens new window) 给定一个有相同值的二叉搜索树BST找出 BST 中的所有众数出现频率最高的元素。 假定 BST 有如下定义 结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的值左子树和右子树都是二叉搜索树 例如 给定 BST [1,null,2,2], 返回[2]. 提示如果众数超过1个不需考虑输出顺序 进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内 思路 如果不是二叉搜索树最直观的方法一定是把这个树都遍历了用map统计频率把频率排个序最后取前面高频的元素的集合。 具体步骤如下 1.这个树都遍历了用map统计频率 2.把统计的出来的出现频率即map中的value排个序 有的同学可能可以想直接对map中的value排序还真做不到C中如果使用std::map或者std::multimap可以对key排序但不能对value排序。 所以要把map转化数组即vector再进行排序当然vector里面放的也是pairint, int类型的数据第一个int为元素第二个int为出现频率。 3.取前面高频的元素 此时数组vector中已经是存放着按照频率排好序的pair那么把前面高频的元素取出来就可以了。 是二叉搜索树那么中序遍历就是一个有序数组遍历有序数组的元素出现频率从头遍历那么一定是相邻两个元素作比较然后就把出现频率最高的元素输出就可以了。 关键是在有序数组上的话好搞在树上怎么搞呢 这就考察对树的操作了。 在二叉树搜索树的最小绝对差 (opens new window)中我们就使用了pre指针和cur指针的技巧这次又用上了。 弄一个指针指向前一个节点这样每次cur当前节点才能和pre前一个节点作比较。 而且初始化的时候pre NULL这样当pre为NULL时候我们就知道这是比较的第一个元素。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:int maxcount0;int count0;vectorintresult;TreeNode prenullptr;void searchBST(TreeNode* cur){if(curnullptr) return;//左searchBST(cur-left);//中//处理次数if(prenullptr){count1;//第一个节点}else if(pre-valcur-val){count;//节点数值相同1}else count1;//节点数值不同重新置1precur;//更新pre;//更新result数组if(countmaxcount) result.push_back(cur-val);else if(countmaxcount){//如果次数大于maxcount,更新maxcount并清空原来结果数组的数值并重新加入maxcountcount;result.clear();result.push_back(cur-val);}searchBST(cur-right);//更新cur;}vectorint findMode(TreeNode* root) {result.clear();searchBST(root);return result;} }; 236. 二叉树的最近公共祖先 力扣题目链接 (opens new window) 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 例如给定如下二叉树:  root  [3,5,1,6,2,0,8,null,null,7,4] 示例 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。因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉树中。 思路 遇到这个题目首先想的是要是能自底向上查找就好了这样就可以找到公共祖先了。 那么二叉树如何可以自底向上查找呢 回溯啊二叉树回溯的过程就是从低到上。 后序遍历左右中就是天然的回溯过程可以根据左右子树的返回值来处理中节点的逻辑。 接下来就看如何判断一个节点是节点q和节点p的公共祖先呢。 首先最容易想到的一个情况如果找到一个节点发现左子树出现结点p右子树出现节点q或者 左子树出现结点q右子树出现节点p那么该节点就是节点p和q的最近公共祖先。 即情况一 判断逻辑是 如果递归遍历遇到q就将q返回遇到p 就将p返回那么如果 左右子树的返回值都不为空说明此时的中节点一定是q 和p 的最近祖先。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };/ class Solution { public:TreeNode lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootq||rootp||rootNULL) return root;TreeNode* leftlowestCommonAncestor(root-left,p,q);//左TreeNode* rightlowestCommonAncestor(root-right,p,q);//右//中注意题目说 p! q且p 和 q 均存在于给定的二叉树中说明肯定能找到pqif(left!nullptrright!nullptr)return root;//在左右子树中找到了那么根就是公共祖先if(leftnullptr) return right;//左子树没找到那就是在右子树中返回右子树根节点return left;} }; 参考代码随想录