算法day16-二叉树（6）
目录[*]530 二叉搜索树的最小绝对差
[*]201 二叉搜索树中的众数
[*]236 二叉树的最近公共祖先（⭐⭐⭐）
一、二叉搜索树的最小绝对差
思路：先按中序遍历输出有序的数组，然后看相邻的元素的差哪个最小。
class Solution {
int res = Integer.MAX_VALUE;
Integer prev = null;
public int getMinimumDifference(TreeNode root) {
inorder(root); //中序遍历起点
return res;
}
public void inorder(TreeNode root){
if(root == null){
return;
}
inorder(root.left);
if(prev != null){
res = Math.min(root.val - prev, res);
}
prev = root.val;
inorder(root.right);
}
}二、二叉搜索树中的众数
https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/?envType=problem-list-v2&envId=8At1GmaZ
思路：按照中序遍历去遍历这棵树。在【中】的逻辑中，先更新该节点出现的次数，然后比较出现次数是否比之前出现过的最多的节点都要多，若是的话则清空res，然后把该节点放进去，更新max的值；若出现的次数与最大的相同，则继续加入到res中。
class Solution {
Map<Integer, Integer> map;
int max;
List<Integer> res;
public int[] findMode(TreeNode root) {
map = new HashMap<>();
res = new ArrayList<>();
max = 0;
inorder(root);
return res.stream().mapToInt(Integer::intValue).toArray();
}
public void inorder(TreeNode root){
if(root == null){
return;
}
inorder(root.left); //----左------
int count = map.getOrDefault(root.val,0)+1; //先统计这个节点出现的次数
map.put(root.val, count);
if(count > max){
res.clear();
res.add(root.val);
max = count;
}else if(count == max){
res.add(root.val);
}
inorder(root.right);
}
}三、二叉树的最近公共祖先
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=problem-list-v2&envId=8At1GmaZ
思路：该题的条件是每个节点的数值都不相同，且一定存在p和q。这里回溯的逻辑需要用后序遍历的方式去做（因为是想从下往上处理）。情况1：左和右都不为空，则中就为最近公共祖先。情况2：根就为p或q，那根就为最近公共祖先。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
if(root == p || root == q){
//如果碰到了这两个节点，则告知上层
return root;
}
TreeNode leftNode = lowestCommonAncestor(root.left,p,q); //告诉我们左子树有没有公共祖先
TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
if(leftNode != null && rightNode != null){
return root;
}
if(leftNode == null && rightNode != null){
return rightNode;
}else if(leftNode != null && rightNode == null){
return leftNode;
}else{
return null;
}
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]