佛山做网站yunzhanfs,温州市永嘉上塘建设局网站,建搜索引擎网站,意识形态建设专题网站530.二叉搜索树的最小绝对差
题目链接#xff1a;530.二叉搜索树的最小绝对差
给你一棵所有节点为非负值的二叉搜索树#xff0c;请你计算树中任意两节点的差的绝对值的最小值。
示例#xff1a; 提示#xff1a;树中至少有 2 个节点。
#x1f4a1;解题思路
题目中…530.二叉搜索树的最小绝对差
题目链接530.二叉搜索树的最小绝对差
给你一棵所有节点为非负值的二叉搜索树请你计算树中任意两节点的差的绝对值的最小值。
示例 提示树中至少有 2 个节点。
解题思路
题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。
注意是二叉搜索树二叉搜索树可是有序的。
遇到在二叉搜索树上求什么最值啊差值之类的就把它想成在一个有序数组上求最值求差值这样就简单多了。
递归
那么二叉搜索树采用中序遍历其实就是一个有序数组。
在一个有序数组上求两个数最小差值这是不是就是一道送分题了。
最直观的想法就是把二叉搜索树转换成有序数组然后遍历一遍数组就统计出来最小差值了。
实现代码
递归class Solution {TreeNode pre;// 记录上一个遍历的结点int result Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(rootnull)return 0;traversal(root);return result;}public void traversal(TreeNode root){if(rootnull)return;//左traversal(root.left);//中if(pre!null){result Math.min(result,root.val-pre.val);}pre root;//右traversal(root.right);}
}統一迭代法-中序遍历class Solution {public int getMinimumDifference(TreeNode root) {StackTreeNode stack new Stack();TreeNode pre null;int result Integer.MAX_VALUE;if(root ! null)stack.add(root);while(!stack.isEmpty()){TreeNode curr stack.peek();if(curr ! null){stack.pop();if(curr.right ! null)stack.add(curr.right);stack.add(curr);stack.add(null);if(curr.left ! null)stack.add(curr.left);}else{stack.pop();TreeNode temp stack.pop();if(pre ! null)result Math.min(result, temp.val - pre.val);pre temp;}}return result;}
}迭代法-中序遍历class Solution {TreeNode pre;StackTreeNode stack;public int getMinimumDifference(TreeNode root) {if (root null) return 0;stack new Stack();TreeNode cur root;int result Integer.MAX_VALUE;while (cur ! null || !stack.isEmpty()) {if (cur ! null) {stack.push(cur); // 将访问的节点放进栈cur cur.left; // 左}else {cur stack.pop(); if (pre ! null) { // 中result Math.min(result, cur.val - pre.val);}pre cur;cur cur.right; // 右}}return result;}
}501.二叉搜索树中的众数
题目链接501.二叉搜索树中的众数
给定一个有相同值的二叉搜索树BST找出 BST 中的所有众数出现频率最高的元素。
假定 BST 有如下定义
结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的值左子树和右子树都是二叉搜索树
例如
给定 BST [1,null,2,2], 返回[2].
提示如果众数超过1个不需考虑输出顺序
进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内
解题思路
递归法
# 如果不是二叉搜索树
如果不是二叉搜索树最直观的方法一定是把这个树都遍历了用map统计频率把频率排个序最后取前面高频的元素的集合。
具体步骤如下
这个树都遍历了用map统计频率
至于用前中后序哪种遍历也不重要因为就是要全遍历一遍怎么个遍历法都行层序遍历都没毛病
这里采用前序遍历代码如下
// mapint, int key:元素value:出现频率
void searchBST(TreeNode* cur, unordered_mapint, int map) { // 前序遍历if (cur NULL) return ;map[cur-val]; // 统计元素频率searchBST(cur-left, map);searchBST(cur-right, map);return ;
}把统计的出来的出现频率即map中的value排个序
有的同学可能可以想直接对map中的value排序还真做不到C中如果使用std::map或者std::multimap可以对key排序但不能对value排序。
所以要把map转化数组即vector再进行排序当然vector里面放的也是pairint, int类型的数据第一个int为元素第二个int为出现频率。
代码如下
bool static cmp (const pairint, int a, const pairint, int b) {return a.second b.second; // 按照频率从大到小排序
}vectorpairint, int vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp); // 给频率排个序取前面高频的元素
此时数组vector中已经是存放着按照频率排好序的pair那么把前面高频的元素取出来就可以了。
代码如下
result.push_back(vec[0].first);
for (int i 1; i vec.size(); i) {// 取最高的放到result数组中if (vec[i].second vec[0].second) result.push_back(vec[i].first);else break;
}
return result;是二叉搜索树
既然是搜索树它中序遍历就是有序的。
如图 中序遍历代码如下
void searchBST(TreeNode* cur) {if (cur NULL) return ;searchBST(cur-left); // 左处理节点 // 中searchBST(cur-right); // 右return ;
}遍历有序数组的元素出现频率从头遍历那么一定是相邻两个元素作比较然后就把出现频率最高的元素输出就可以了。
实现代码
class Solution {ArrayListInteger resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {resList new ArrayList();maxCount 0;count 0;pre null;findMode1(root);int[] res new int[resList.size()];for (int i 0; i resList.size(); i) {res[i] resList.get(i);}return res;}public void findMode1(TreeNode root) {if (root null) {return;}findMode1(root.left);int rootValue root.val;// 计数if (pre null || rootValue ! pre.val) {count 1;} else {count;}// 更新结果以及maxCountif (count maxCount) {resList.clear();resList.add(rootValue);maxCount count;} else if (count maxCount) {resList.add(rootValue);}pre root;findMode1(root.right);}
}236. 二叉树的最近公共祖先
题目链接236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 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 的最近祖先。
实现代码
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null || root p || root q) { // 递归结束条件return root;}// 后序遍历TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if(left null right null) { // 若未找到节点 p 或 qreturn null;}else if(left null right ! null) { // 若找到一个节点return right;}else if(left ! null right null) { // 若找到一个节点return left;}else { // 若找到两个节点return root;}}
}
