目录
- 530 二叉搜索树的最小绝对差
- 201 二叉搜索树中的众数
- 236 二叉树的最近公共祖先(⭐⭐⭐)
一、二叉搜索树的最小绝对差
思路:先按中序遍历输出有序的数组,然后看相邻的元素的差哪个最小。- class Solution {
- int res = Integer.MAX_VALUE;
- Integer prev = null;
- public int getMinimumDifference(TreeNode root) {
- inorder(root); //中序遍历起点
- return res;
- }
- public void inorder(TreeNode root){
- if(root == null){
- return;
- }
- inorder(root.left);
- if(prev != null){
- res = Math.min(root.val - prev, res);
- }
- prev = root.val;
- inorder(root.right);
- }
- }
复制代码 二、二叉搜索树中的众数
https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/?envType=problem-list-v2&envId=8At1GmaZ
思路:按照中序遍历去遍历这棵树。在【中】的逻辑中,先更新该节点出现的次数,然后比较出现次数是否比之前出现过的最多的节点都要多,若是的话则清空res,然后把该节点放进去,更新max的值;若出现的次数与最大的相同,则继续加入到res中。- class Solution {
- Map<Integer, Integer> map;
- int max;
- List<Integer> res;
- public int[] findMode(TreeNode root) {
- map = new HashMap<>();
- res = new ArrayList<>();
- max = 0;
- inorder(root);
- return res.stream().mapToInt(Integer::intValue).toArray();
- }
- public void inorder(TreeNode root){
- if(root == null){
- return;
- }
- inorder(root.left); //----左------
- int count = map.getOrDefault(root.val,0)+1; //先统计这个节点出现的次数
- map.put(root.val, count);
- if(count > max){
- res.clear();
- res.add(root.val);
- max = count;
- }else if(count == max){
- res.add(root.val);
- }
- inorder(root.right);
- }
- }
复制代码 三、二叉树的最近公共祖先
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=problem-list-v2&envId=8At1GmaZ
思路:该题的条件是每个节点的数值都不相同,且一定存在p和q。这里回溯的逻辑需要用后序遍历的方式去做(因为是想从下往上处理)。情况1:左和右都不为空,则中就为最近公共祖先。情况2:根就为p或q,那根就为最近公共祖先。- class Solution {
- public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if(root == null){
- return null;
- }
- if(root == p || root == q){
- //如果碰到了这两个节点,则告知上层
- return root;
- }
- TreeNode leftNode = lowestCommonAncestor(root.left,p,q); //告诉我们左子树有没有公共祖先
- TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
- if(leftNode != null && rightNode != null){
- return root;
- }
- if(leftNode == null && rightNode != null){
- return rightNode;
- }else if(leftNode != null && rightNode == null){
- return leftNode;
- }else{
- return null;
- }
- }
- }
复制代码
来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |