找回密码
 立即注册
首页 业界区 科技 算法day16-二叉树(6)

算法day16-二叉树(6)

轨项尺 2025-6-7 10:15:36
目录


  • 530 二叉搜索树的最小绝对差
  • 201 二叉搜索树中的众数
  • 236 二叉树的最近公共祖先(⭐⭐⭐)
一、二叉搜索树的最小绝对差

1.png

   思路:先按中序遍历输出有序的数组,然后看相邻的元素的差哪个最小。
  1. class Solution {
  2.     int res = Integer.MAX_VALUE;
  3.     Integer prev = null;
  4.     public int getMinimumDifference(TreeNode root) {
  5.         inorder(root);      //中序遍历起点
  6.         return res;
  7.     }
  8.     public void inorder(TreeNode root){
  9.         if(root == null){
  10.             return;
  11.         }
  12.         inorder(root.left);
  13.         if(prev != null){
  14.             res = Math.min(root.val - prev, res);
  15.         }
  16.         prev = root.val;
  17.         inorder(root.right);
  18.     }
  19. }
复制代码
二、二叉搜索树中的众数

 https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/?envType=problem-list-v2&envId=8At1GmaZ
2.png

   思路:按照中序遍历去遍历这棵树。在【中】的逻辑中,先更新该节点出现的次数,然后比较出现次数是否比之前出现过的最多的节点都要多,若是的话则清空res,然后把该节点放进去,更新max的值;若出现的次数与最大的相同,则继续加入到res中。
  1. class Solution {
  2.     Map<Integer, Integer> map;
  3.     int max;
  4.     List<Integer> res;
  5.     public int[] findMode(TreeNode root) {
  6.         map = new HashMap<>();
  7.         res = new ArrayList<>();
  8.         max = 0;
  9.         inorder(root);
  10.         return res.stream().mapToInt(Integer::intValue).toArray();
  11.     }
  12.     public void inorder(TreeNode root){
  13.         if(root == null){
  14.             return;
  15.         }
  16.         inorder(root.left);        //----左------
  17.         int count = map.getOrDefault(root.val,0)+1; //先统计这个节点出现的次数
  18.         map.put(root.val, count);
  19.         if(count > max){
  20.             res.clear();
  21.             res.add(root.val);
  22.             max = count;
  23.         }else if(count == max){
  24.             res.add(root.val);
  25.         }
  26.         inorder(root.right);
  27.     }
  28. }
复制代码
三、二叉树的最近公共祖先

 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=problem-list-v2&envId=8At1GmaZ
3.png

   思路:该题的条件是每个节点的数值都不相同,且一定存在p和q。这里回溯的逻辑需要用后序遍历的方式去做(因为是想从下往上处理)。情况1:左和右都不为空,则中就为最近公共祖先。情况2:根就为p或q,那根就为最近公共祖先。
  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root == null){
  4.             return null;
  5.         }
  6.         if(root == p || root == q){
  7.             //如果碰到了这两个节点,则告知上层
  8.             return root;
  9.         }
  10.         TreeNode leftNode = lowestCommonAncestor(root.left,p,q);    //告诉我们左子树有没有公共祖先
  11.         TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
  12.         if(leftNode != null && rightNode != null){
  13.             return root;
  14.         }
  15.         if(leftNode == null && rightNode != null){
  16.             return rightNode;
  17.         }else if(leftNode != null && rightNode == null){
  18.             return leftNode;
  19.         }else{
  20.             return null;
  21.         }
  22.     }
  23. }
复制代码
 

来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
您需要登录后才可以回帖 登录 | 立即注册