网站名字重复,国外酷炫flash网站,库存管理软件哪个好用,如何学习网站制作530. 二叉搜索树的最小绝对差
题目链接
题目描述#xff1a; 给你一棵所有节点为非负值的二叉搜索树#xff0c;请你计算树中任意两节点的差的绝对值的最小值。
示例#xff1a; 提示#xff1a;树中至少有 2 个节点。
难点#xff1a;
解答错误#xff01;仅考虑了…530. 二叉搜索树的最小绝对差
题目链接
题目描述 给你一棵所有节点为非负值的二叉搜索树请你计算树中任意两节点的差的绝对值的最小值。
示例 提示树中至少有 2 个节点。
难点
解答错误仅考虑了相邻漏掉了不相邻的情况与根节点之差
class Solution {public int getMinimumDifference(TreeNode root) {//最小差值一定是相邻接的节点子树某个根节点和左右孩子//采用中序遍历就可以if (root null) return Integer.MAX_VALUE;int left, right;if (root.left ! null) {left Math.min(getMinimumDifference(root.left), root.val - root.left.val);}else {left Integer.MAX_VALUE;}if (root.right ! null) {right Math.min(getMinimumDifference(root.right), root.right.val - root.val);}else {right Integer.MAX_VALUE;}return Math.min(left, right);}
}在中序遍历中要记录上一个遍历的节点
class Solution {TreeNode pre;int result Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {//采用中序遍历traversal(root);return result;}private void traversal(TreeNode root) {if (root null) return;traversal(root.left);if (pre ! null) {result Math.min(result, root.val - pre.val);}pre root;traversal(root.right);}
}时长 15min
收获 中序遍历记录上一个遍历的节点 501. 二叉搜索树中的众数
题目链接
题目描述 给定一个有相同值的二叉搜索树BST找出 BST 中的所有众数出现频率最高的元素。
假定 BST 有如下定义
结点左子树中所含结点的值小于等于当前结点的值 结点右子树中所含结点的值大于等于当前结点的值 左子树和右子树都是二叉搜索树 例如
给定 BST [1,null,2,2], 返回[2].
提示如果众数超过1个不需考虑输出顺序
进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内
难点
思路
时间复杂度O() 空间复杂度O()
class Solution {int cnt;int maxNum;TreeNode pre;ListInteger result new ArrayList();public int[] findMode(TreeNode root) {searchBST(root);return result.stream().mapToInt(Integer::intValue).toArray();}private void searchBST(TreeNode root) {if (root null) return;searchBST(root.left);if (pre null) { //第一个节点cnt 1;}else if(pre.val root.val) { //相同值计数cnt;}else { //不同值计数器重置1cnt 1;}pre root;if (cnt maxNum) {result.add(root.val);}if (cnt maxNum) {result.clear();result.add(root.val);maxNum cnt;}searchBST(root.right);}
}时长 22min
收获 使用双指针记录上一个遍历的节点
将ArrayList Integer 转化为int[]数组的方式 result.stream().mapToInt(Integer::intValue).toArray(); 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 为不同节点且均存在于给定的二叉树中。
难点
思路
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root p || root q || root null) return root;TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if (left ! null right ! null) return root;if (left null right ! null) return right;if (left ! null right null) return left;return null;}
}时长 20min
收获 有难度的一题思路好好再捋一捋
