算法训练Day21|530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

 1class Solution {
 2    TreeNode pre; // 存储前一个节点
 3    int ans = Integer.MAX_VALUE; // 取最小值，因此以最大值为边界
 4
 5    public int getMinimumDifference(TreeNode root) {
 6        // if (root == null) return 0; // 节点数大于2，所以应该省略
 7        traversal(root); // 单层递归函数
 8        return ans; // 返回最小绝对差值：ans
 9    }
10
11    // 构建单层递归的逻辑，传入参数节点root/cur
12    public void traversal(TreeNode root) { 
13        // 确定终止条件 
14        if (root == null) return; // 判断当前节点是否为空，为空直接返回，否则继续递归
15        // 左：向左递归遍历，从叶子节点算起
16        traversal(root.left);
17        // 中：中节点处理逻辑
18        if (pre != null) { // 前节点pre不为空
19            ans = Math.min(ans, root.val - pre.val); // 选取ans和当前节点与前一节点差值的较小值
20        }
21        pre = root; // 将当前节点赋值给前节点pre，双指针法的体现！！！
22        // 右：向右递归遍历，从右子树叶子节点算起...
23        traversal(root.right);
24    }
25}

 1class Solution {
 2    // 定义全局变量
 3    ArrayList<Integer> resList = new ArrayList<>(); // list链表存储结果
 4    int maxCount = 0; // 记录众数的大小
 5    int count = 0; // 计数器
 6    TreeNode pre = null; // 前节点
 7
 8    public int[] findMode(TreeNode root) {
 9        // 调用递归函数
10        traversal(root);
11
12        // 将众数值存储数组中，进行记录返回
13        int[] res = new int[resList.size()]; // 创建一个存储众数结果的数组
14        for (int i = 0; i < resList.size(); i++) { 
15            res[i] = resList.get(i); // 将众数的值装入res数组中
16        }
17        return res; // 返回结果
18
19    }
20    // 构建单层递归的逻辑
21    public void traversal(TreeNode root) {
22        if (root == null) return; // 如果节点为空，直接返回
23        // 左：向左遍历
24        traversal(root.left); 
25
26        // 中：计数器用于记录每个节点的众数值
27        if (pre == null || root.val != pre.val) {
28            count = 1; // 前节点为null活当前节点与前节点不等时，该数出现频率为1
29        } else {
30            count++; // 否则进行累加
31        }
32        // 获取众数值最大的值并写入相应的节点值root.val
33        if (count > maxCount) {
34            resList.clear();
35            resList.add(root.val);
36            maxCount = count;
37        } else if (count == maxCount) { // 如果遇到众数值相等时，则将其节点值加入其中
38            resList.add(root.val);
39        }
40        pre = root; // 更新前一节点pre到当前节点
41        // 右：更新当前节点向右遍历
42        traversal(root.right);
43    }
44}

 1class Solution {
 2    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 3        // 确定递归函数的参数及返回值
 4        if (root == null || root == p || root == q) {
 5            return root;
 6        }
 7        // 记录返回值，使用回溯；回溯则使用后序遍历
 8        // 左：
 9        TreeNode left = lowestCommonAncestor(root.left, p, q);
10        // 右
11        TreeNode right = lowestCommonAncestor(root.right, p, q);
12        // 中：做回溯操作...
13        if (left == null && right == null) { // 左右节点均为null，不存在最小公共祖先，返回null即可
14            return null;
15        } else if (left != null && right == null) { // 左节点存在一个p或q，右节点为空，返回左节点即可
16            return left;
17        } else if (left == null && right != null) { // 右节点存在一个p或q，左节点为null,返回右节点即可
18            return right;
19        } else {
20            return root; // 左右节点均不为空，则该节点即为p和q的最小公共祖先，返回即可
21        }
22    }
23}