算法day16-二叉树（6）

目录

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

一、二叉搜索树的最小绝对差

 　　思路：先按中序遍历输出有序的数组，然后看相邻的元素的差哪个最小。

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

 　　思路：按照中序遍历去遍历这棵树。在【中】的逻辑中，先更新该节点出现的次数，然后比较出现次数是否比之前出现过的最多的节点都要多，若是的话则清空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);
20.         if(count > max){
21.             res.clear();
22.             res.add(root.val);
23.             max = count;
24.         }else if(count == max){
25.             res.add(root.val);
26.         }
27.         inorder(root.right);
28.     }
29. }

复制代码

三、二叉树的最近公共祖先

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

 　　思路：该题的条件是每个节点的数值都不相同，且一定存在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);
13.         if(leftNode != null && rightNode != null){
14.             return root;
15.         }
16.         if(leftNode == null && rightNode != null){
17.             return rightNode;
18.         }else if(leftNode != null && rightNode == null){
19.             return leftNode;
20.         }else{
21.             return null;
22.         }
23.     }
24. }

复制代码

 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！