当前位置：首页 > article >正文

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

article 2024/9/27 9:21:56

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

题目：给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

提示：

树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

思路：根据二叉搜索树的性质可知，中序遍历后得到一个不重复的单调递增数组，对该数组进行差值比较即可得到最小差值。

升级思路：中序遍历时，记录前一个遍历节点的值，得到当前节点与前一个节点的差值，更新得到最小差值，本思路只需要遍历一次二叉树即可。

注意： 升级思路中，遍历第一个节点时要根据前一个节点pre是否为空进行判断。

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int minDiff = Integer.MAX_VALUE;
    TreeNode pre ;
    public int getMinimumDifference(TreeNode root) {
        
        inOrder(root);
        return minDiff;
    }

    private void inOrder(TreeNode root){
        if(root == null){
            return ;
        }
        inOrder(root.left);
        if(pre !=null){
            minDiff = Math.min(minDiff,root.val-pre.val);
        }
        pre = root;
        inOrder(root.right);
    }

    
    // ArrayList<Integer> point = new ArrayList<Integer>();
    // public int getMinimumDifference(TreeNode root) {
        
    //     inOrder(root);
    //     return minDifference(point);
    // }

    // private void inOrder(TreeNode root){
    //     if(root == null){
    //         return ;
    //     }
    //     inOrder(root.left);
    //     point.add(root.val);
    //     inOrder(root.right);
    // }

    // private int minDifference(ArrayList<Integer> point){
    //     int min = point.get(point.size()-1);
    //     for(int i = point.size() -1;i>0;i--){
    //         if(point.get(i)-point.get(i-1)<min){
    //             min = point.get(i)-point.get(i-1);
    //         }
    //     }
    //     return min;
    // }
    
}

2 501. 二叉搜索树中的众数

题目： 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。如果树中有不止一个众数，可以按 任意顺序 返回。假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

思路：最直接的做法是遍历二叉树，将节点值和出现次数加入map中，对map中元素排序得到结果。

升级思路：中序遍历二叉树，并在遍历过程中记录元素的出现次数，将出现次数最大的元素保存到res数组中记录下来。

注意：出现次数随着每次计数而刷新，当出现新的最大计数时，res中元素要清空并更新最大计数值。

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 // 利用搜索二叉树特性，一次性遍历得出众数集合
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;
    }

    private 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){
            maxCount = count;
            resList.clear();
            resList.add(rootValue);
        }else if(count == maxCount){
            resList.add(rootValue);
        }
        
        pre = root;

        findMode1(root.right);
    }


}

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

题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

思路：本题从下向上寻找比较方便，确定p和q的子树后找到他们的离他们最近的共同祖先，即深度最大的公共祖先。采用后续遍历的方法，左右中，逻辑上的从下至上。当找到p或q时，返回找到的节点，若都找到时，就可以返回公共祖先。

注意：公共祖先可以为q或p自身，因此在判断时，root为空或者root等于q或者root等于p要可以返回root。

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为空，或者p,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 null;
        }
        if(left == null && right != null){
            return right;
        }
        if(left != null && right == null){
            return left;
        }else{
            return root;
        }
        
    }
}

查看全文

http://www.kler.cn/news/319697.html