国外网站博客网站也可以做引流,丹东seo营销,wordpress 更换服务器,成都百度推广公司电话随想录日记part17 t i m e #xff1a; time#xff1a; time#xff1a; 2024.03.12 主要内容#xff1a;今天的主要内容是二叉树的第六部分#xff0c;主要涉及二叉搜索树的最小绝对差 #xff1b;二叉搜索树中的众数#xff1b;二叉树的最近公共祖先。 530.二叉搜索树…随想录日记part17 t i m e time time 2024.03.12 主要内容今天的主要内容是二叉树的第六部分主要涉及二叉搜索树的最小绝对差 二叉搜索树中的众数二叉树的最近公共祖先。 530.二叉搜索树的最小绝对差501.二叉搜索树中的众数236. 二叉树的最近公共祖先 Topic1二叉搜索树的最小绝对差
题目 给你一个二叉搜索树的根节点 r o o t root root 返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数其数值等于两值之差的绝对值。 示例 输入 r o o t [ 4 , 2 , 6 , 1 , 3 ] root [4,2,6,1,3] root[4,2,6,1,3] 输出 1 1 1
思路 把二叉搜索树转换成有序数组然后遍历一遍数组就统计出来最小差值:direct/b54a915741f74f9ab515b28243d24f40.gif) 总体代码如下 class Solution {int result Integer.MAX_VALUE;TreeNode pre;// 记录上个节点public int getMinimumDifference(TreeNode root) {if (root null)return 0;center_search(root);return result;}private void center_search(TreeNode root) {// 中序遍历if (root null)return;// 左center_search(root.left);// 中if (pre ! null)result Math.min(result, root.val - pre.val);pre root;// 右center_search(root.right);}
}Topic2二叉搜索树中的众数
题目 给你一个含重复值的二叉搜索树 B S T BST BST 的根节点 r o o t root root 找出并返回 B S T BST BST 中的所有众数即出现频率最高的元素。 如果树中有不止一个众数可以按任意顺序返回。 假定 BST 满足如下定义 结点左子树中所含节点的值 小于等于 当前节点的值结点右子树中所含节点的值 大于等于 当前节点的值左子树和右子树都是二叉搜索树 输入 r o o t [ 1 , n u l l , 2 , 2 ] ] root [1,null,2,2]] root[1,null,2,2]] 输出 [ 2 ] [2] [2]
思路 既然是搜索树它中序遍历就是有序的。 如图 总体代码如下 递归法 class Solution {// 定义一些辅助数据ArrayListInteger resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {resList new ArrayList();maxCount 0;count 0;check(root);int[] nums new int[resList.size()];for (int i 0; i resList.size(); i) {nums[i] resList.get(i);}return nums;}private void check(TreeNode root) {if (root null)return;// 左check(root.left);// 中if (pre null || root.val ! pre.val) {count 1;} else {count;}if (count maxCount) {resList.clear();resList.add(root.val);maxCount count;} else if (count maxCount) {resList.add(root.val);}pre root;check(root.right);}
}Topic3二叉树的最近公共祖先
题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T T T 的两个节点 p 、 q p、q p、q最近公共祖先表示为一个节点 x x x满足 x x x 是 p 、 q p、q p、q 的祖先且 x x x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例
输入 r o o t [ 3 , 5 , 1 , 6 , 2 , 0 , 8 , n u l l , n u l l , 7 , 4 ] , p 5 , q 1 root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 root[3,5,1,6,2,0,8,null,null,7,4],p5,q1 输出 3 3 3
思路 后序遍历递归法 代码如下 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)return root;if (left ! null right null)return left;else if (left null right ! null)return right;elsereturn null;}
}
