代码随想录算法训练营（JAVA）| 第六章二叉树part07

今日任务

力扣 530. 二叉搜索树的最小绝对差，501. 二叉搜索树中的众数

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

思路

注意是二叉搜索树，二叉搜索树可是有序的。

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值

那么二叉搜索树采用中序遍历，其实就是一个有序数组。

在一个有序数组上求两个数最小差值，这是不是就是一道送分题了。

最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。

递归

那么二叉搜索树采用中序遍历，其实就是一个有序数组。

在一个有序数组上求两个数最小差值，这是不是就是一道送分题了。

最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。

如何转换成有序数组？----需要一个pre节点

具体如何实现请看代码

题解

java">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. 二叉搜索树中的众数

思路

哈希表呗，先都存进去在找最大的

是二叉搜索树

既然是搜索树，它中序遍历就是有序的。

寸止！先让我们来学习一下

普通二叉树是如何寻找众数：总共需要遍历二遍

这个树都遍历了，用map统计频率
把统计的出来的出现频率（即map中的value）排个序
取前面高频的元素

二叉搜索树：总共只需要遍历一遍

把握搜索树，中序遍历就是有序的的特性。

图中实线为遍历后的结果

中序遍历-伪代码

java">void searchBST(TreeNode cur) {
    if (cur == NULL) return ;
    searchBST(cur.left);       // 左
    （处理节点）                // 中
    searchBST(cur.right);      // 右
    return ;
}

利用性质中序遍历转换成升序排列
遍历有序数组的元素出现频率 一边遍历一边比较动态寻找最大值

而在本题中“最大频率的数可能不止有一个”，因此需要动态调整最大频率和最大频率值。

统计频率-伪代码

java">if (pre == NULL) { // 第一个节点
    count = 1; // 频率为1
} else if (pre.val == cur.val) { // 与前一个节点数值相同
    count++;
} else { // 与前一个节点数值不同
    count = 1;
}
pre = cur; // 更新上一个节点

查找最值-伪代码

频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。

java">        if (count > maxConut)
        {
            resList.add(rootValue); // 更新最大频率
            resList.clear();  // 很关键的一步，不要忘记清空result，之前result里的元素都失效了

            maxConut = count;
        } else if (count == maxConut) {
            resList.add(rootValue);
        }

题解

普通二叉树实现

在这段代码中：

我们定义了一个countMap来记录每个数值出现的次数。
traverse方法用于递归遍历整棵树，同时更新countMap。
在遍历结束后，我们遍历countMap来找到出现次数等于maxCount的所有数值，这些就是众数。
最后，我们把众数列表转换成数组并返回。

这种方法不依赖于二叉搜索树的性质，适用于任何二叉树。不过，它的空间复杂度相对较高，因为需要存储树中所有不同值的计数。

java">import java.util.*;


class Solution {
    private Map<Integer, Integer> countMap = new HashMap<>();
    private int maxCount = 0;

    public int[] findMode(TreeNode root) {
        traverse(root);

        List<Integer> modes = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() == maxCount) {
                modes.add(entry.getKey());
            }
        }

        int[] result = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            result[i] = modes.get(i);
        }
        return result;
    }

    private void traverse(TreeNode node) {
        if (node == null) return;
        countMap.put(node.val, countMap.getOrDefault(node.val, 0) + 1);
        int count = countMap.get(node.val);
        maxCount = Math.max(maxCount, count);

        traverse(node.left);
        traverse(node.right);
    }
}

二叉搜索树

中序遍历-不使用额外空间，利用二叉搜索树特性

java">class Solution {
    ArrayList<Integer> resList = new ArrayList<>();
    int maxConut, count;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        pre = null;
        func(root);
        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++ ) 
        {
            res[i] = resList.get(i);
        }
        return res;
    }

    public void func(TreeNode root) {
        if (root == null) return;
        func(root.left);

        int rootValue = root.val;
        if (pre == null || rootValue != pre.val)
        {
            // 重置值
            count = 1;
        } else
        {
            count++;
        }

        if (count > maxConut)
        {
            resList.clear();
            resList.add(rootValue);
            maxConut = count;
        } else if (count == maxConut) {
            resList.add(rootValue);
        }
        pre = root;

        func(root.right);
    }
}

迭代法

java">class Solution {
    public int[] findMode(TreeNode root) {
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        int maxCount = 0, count = 0;
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty())
        {
            if (cur != null)
            {
                stack.push(cur);
                cur = cur.left;
            } else 
            {
                cur = stack.pop();

                if (pre == null || cur.val != pre.val)
                {
                    count = 1;
                } else 
                {
                    count++;
                }

                if (count > maxCount)
                {
                    maxCount = count;
                    result.clear();
                    result.add(cur.val);
                } else if (count == maxCount)
                {
                    result.add(cur.val);
                }

                pre = cur;
                cur = cur.right;
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}