【Java】代码随想录二叉树07| LeetCode530 二叉搜索树的最小绝对差、LeetCode501二叉搜索树中的众数、LeetCode236二叉树的最近公共组先

目录

二叉树07

LeetCode530 二叉搜索树的最小绝对差

LeetCode501 二叉搜索树中的众数

LeetCode236 二叉树的最近公共组先

---

二叉树07

LeetCode530 二叉搜索树的最小绝对差

思路：由于二叉搜索树中序遍历就是一个就是一个有序数组，那么就转变成了在有序数组上求最小绝对差值。

在这个过程中，由于要比较，因此要用一个pre节点来记录前一个root，类似于双指针法

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);
    }
}

---

LeetCode501 二叉搜索树中的众数

思路：

如果是普通二叉树，第一反应是用map存储

class Solution {
	public int[] findMode(TreeNode root) {
		Map<Integer, Integer> map = new HashMap<>();
		List<Integer> list = new ArrayList<>();
		if (root == null) return list.stream().mapToInt(Integer::intValue).toArray();
		// 获得频率 Map，这是降序，所以数组的第一个元素就是频率最高的元素
		searchBST(root, map);
		List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
				.sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
				.collect(Collectors.toList());
		list.add(mapList.get(0).getKey());
		// 把频率最高的加入 list，并且可能有频率相同的多个众数
		for (int i = 1; i < mapList.size(); i++) {
			if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {
				list.add(mapList.get(i).getKey());
			} else {
				break;
			}
		}
        //把list里的元素转化成int类型数组
		return list.stream().mapToInt(Integer::intValue).toArray();
	}
 
	void searchBST(TreeNode curr, Map<Integer, Integer> map) {
		if (curr == null) return;
		map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);
		searchBST(curr.left, map);
		searchBST(curr.right, map);
	}
 
}

但是已知这是二叉搜索树，所以第一反应是通过pre来进行比较

• 仍然使用中序遍历
• 中间的逻辑：比较当前节点和pre，如果pre为空，则是第一个节点，count==1；如果与pre和cur的值相同，则count++；如果不相同，则count还是等于1
• 得到频率数组后，怎么得到众数：普通的做法（两次遍历）——首先遍历频率数组找到最大频率maxCount，然后再遍历一遍找到最大频率maxCount对应的数，放入结果集。一次遍历——如果count等于maxCount，把对应的数加入res数组；如果大于，则更新maxCount，清空res数组，重新加入众数。

class Solution {
    //全局变量
    int count = 0;
    int maxCount = 0;
    TreeNode pre = null;
    List<Integer> res = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        traversal(root);    //递归后res里已经得出了众数结果
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
    public void traversal(TreeNode root){
        if(root == null){
            return;
        }
        traversal(root.left);
        //首先计算count
        if(pre == null || root.val != pre.val){
            count = 1;
        }else{
            count++;
        }
        //然后通过比较count和maxcount实现单次遍历找到众数
        if(maxCount == count){
            res.add(root.val);
        }else if(count > maxCount){
            maxCount = count;
            res.clear();
            res.add(root.val);
        }
        pre = root; //更新pre
        traversal(root.right);
    }
}

---

LeetCode236 二叉树的最近公共组先

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

那么既然要找公共祖先且深度要尽可能大，最方便就是自底向上查找

• 回溯就是从低向上的过程，且后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。
• 最近公共祖先：（情况1）如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。（情况2）p在q的子树或者q在p的子树。
• 构造递归函数：首先，传入参数是root，p，q，返回值是最近公共祖先Treenode；其次，终止条件是root为空，除此之外还有p、q为root时都返回root；单层递归是这样的，左，右，中间对left和right进行逻辑处理，即左右都不为空，return root；左或右单边为空，返回不为空的右或左；左中右都为空，返回左右都行。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null | p == root | q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null) return root;
        else if(left == null && right != null) return right;
        else if(left != null && right == null) return left;
        else return null;
    }
}