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

题目链接

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/

题目描述

思路

遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。二叉树的中序遍历是从小到大的顺序

1、中序+遍历

先中序遍历得到二叉搜索树的有序数组，再遍历一遍数组，找到最小差值

class Solution {
    public int getMinimumDifference(TreeNode root) {
        int min = Integer.MAX_VALUE;
        List<Integer> list = new ArrayList<>();
        midorder(root,list);
        for (int i = 1; i < list.size(); i++) {
            min = Math.min(min,list.get(i)-list.get(i-1));
        }
        return min;
    }

    private static void midorder(TreeNode root,List<Integer> list){
        if(root==null) return;
        midorder(root.left,list);
        list.add(root.val);
        midorder(root.right,list);
    }
}

2、双指针

class Solution {
    TreeNode pre;// 记录上一个遍历的结点
    int result = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
       if(root==null)return 0;
       traversal(root);
       return result;
    }
    public 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);
    }
}

501.二叉搜索树中的众数

题目链接

https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/

题目描述

思路

将每个节点以及节点出现的次数存放到map集合中，遍历集合的值，找到最大的即出现次数最多的，再找到出现次数为最大值的所有键

class Solution {
    public int[] findMode(TreeNode root) {
        Map<Integer,Integer> map = new HashMap<>();
        midorder(root,map);
        int maxValue = 0;
        //找出出现次数最多的值
        for (Integer value : map.values()) {
            maxValue = Math.max(maxValue,value);
        }
        //找到出现次数最多对应的键值
        //创建一个数组存放出现次数最多的值
        List<Integer> list = new ArrayList<>();
        for (Integer integer : map.keySet()) {
            if(map.get(integer)==maxValue){
                list.add(integer);
            }
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
    private void midorder(TreeNode root, Map<Integer,Integer> map){
        if(root==null) return;
        midorder(root.left,map);
        map.put(root.val, map.getOrDefault(root.val,0)+1);
        midorder(root.right,map);
    }
}

思路2

findMode1函数中，按照中序遍历去进行判断pre为空（即刚开始）或者pre！=当前节点值（说明已经开始计算下一个节点的出现次数了）的时候，都将count置为1
只有pre==当前节点值的时候，才将count加加；
接下来去判断count和maxCount，刚开始会把一些无关的都添加到列表中，但是在比较的过程中会不断的更新maxCount，所以需要清空列表去添加最大的，最后在主函数中调用这个函数，再用数组去存储

class Solution {
    ArrayList<Integer> 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++;
        }
        // 更新结果以及maxCount
        if (count > maxCount) {
            resList.clear();
            resList.add(rootValue);
            maxCount = count;
        } else if (count == maxCount) {
            resList.add(rootValue);
        }
        pre = root;

        findMode1(root.right);
    }
}

236. 二叉树的最近公共祖先

题目链接

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

题目描述

思路

没太明白

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 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点
            return right;
        }else if(left != null && right == null) { // 若找到一个节点
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }
}