代码随想录算法训练营第十八天-530二叉搜索树的最小绝对差、501二叉搜索树中的众数、236二叉树的最近公共祖先

• 前言
  状态：530 暴力遍历、501 暴力、236 不会。看了昨天的题解把 530 改成了双指针。

• 更新

24.06.08 初始记录

初步题解

530 二叉搜索树的最小绝对差

题目链接：(https://leetcode.cn/problems/minimum-absolute-difference-in-bst)

// 暴力遍历
public int getMinimumDifference(TreeNode root) {  
    List<Integer> list = new ArrayList<>();  
    getMinDiff(root, list);  
    int min = Math.abs(list.get(0) - list.get(1));  
  
    for (int i = 2; i < list.size(); i++) {  
        min = Math.min(Math.abs(list.get(i) - list.get(i - 1)), min);  
    }  
  
    return min;  
}  
  
private void getMinDiff(TreeNode root, List<Integer> list) {  
    if (root == null) {  
        return;  
    }  
  
    getMinDiff(root.left, list);  
    list.add(root.val);  
    getMinDiff(root.right, list);  
}
// 后面看了昨天最后一题的题解，这里可以用双指针
/**  
 * 双指针的解法  
 * @param root 根节点  
 */  
Integer min = Integer.MAX_VALUE;  
TreeNode pre;  
public int getMinimumDifference1(TreeNode root) {  
    if (root == null) {  
        return min;  
    }  
  
    getMinimumDifference1(root.left);  
  
    // 中间遍历  
    if (pre != null) {  
        min = Math.min(Math.abs(root.val - pre.val), min);  
    }  
    pre = root;  
  
    getMinimumDifference1(root.right);  
  
    return min;  
}

501 二叉搜索树中的众数

题目链接：(https://leetcode.cn/problems/find-mode-in-binary-search-tree)

public static int[] findMode(TreeNode root) {  
    if (root == null) {  
        return new int[]{};  
    }  
  
    Map<Integer, Integer> map = new HashMap<>();  
    find(root, map);  
    List<Map.Entry<Integer, Integer>> collect = map.entrySet().stream()  
            .sorted((o1, o2) -> o2.getValue() - o1.getValue())  
            .collect(Collectors.toList());  
    List<Integer> list = new ArrayList<>();  
    list.add(collect.get(0).getKey());  
    for (int i = 1; i < collect.size(); i++) {  
        if (collect.get(i).getValue().equals(collect.get(0).getValue())) {  
            list.add(collect.get(i).getKey());  
        }  
    }  
    return list.stream().mapToInt(i -> i).toArray();  
}  
  
private static void find(TreeNode root, Map<Integer, Integer> map) {  
    if (root == null){  
        return;  
    }  
  
    find(root.left, map);  
    map.put(root.val, map.getOrDefault(root.val, 0) + 1);  
    find(root.right, map);  
}

236 二叉树的最近公共祖先

题目链接：(https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree)

没有思路。

看解析

530 二叉搜索树的最小绝对差

题目链接/文章讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html

视频讲解：https://www.bilibili.com/video/BV1DD4y11779

501 二叉搜索树中的众数

题目链接/文章讲解：https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html

视频讲解：https://www.bilibili.com/video/BV1fD4y117gp

// 双指针的前一个节点  
TreeNode pre = null;  
int count = 0;  
int maxCount = 0;  
  
/**  
 * 双指针解法  
 * @param root 根节点  
 * @return 结果  
 */  
public int[] findMode(TreeNode root) {  
    List<Integer> list = new ArrayList<>();  
  
    // 递归逻辑  
    findModeTravel(root, list);  
  
    return list.stream().mapToInt(i -> i).toArray();  
}  
  
private void findModeTravel(TreeNode root, List<Integer> list) {  
    if (root == null) {  
        return;  
    }  
  
    findModeTravel(root.left, list);  
  
    if (pre == null) {  
        count = 1;  
    }else if (pre.val == root.val){  
        count++;  
    } else {  
        count = 1;  
    }  
    pre = root;  
  
    if (count == maxCount) {  
        list.add(root.val);  
    } else if (count > maxCount) {  
        maxCount = count;  
        list.clear();  
        list.add(root.val);  
    }  
  
    findModeTravel(root.right, list);  
}

236 二叉树的最近公共祖先

题目链接/文章讲解：https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
    // return root也是空 可以和下面一起写  
    if (root == null) {  
        return null;  
    }  
    if (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;  
    } else if (left != null && right == null) {  
        return left;  
    } else if (right != null && left == null) {  
        return right;  
    } else {  
        return null;  
    }  
}