代码随想录day18 | leetcode 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236.二叉树的最近公共祖先

标签：遍历 递归 随想录 二叉 搜索 当前 maxCount root 节点

刷题收获

所有递归的写法都与正常人类想法的实现顺序相反,都是先写条件成立会发生什么 再写递归成立条件

通过递归调用栈实现回到上一个节点节点（恢复上一层的状态），调用栈能够记录每次递归调用的函数状态，包括函数的局部变量、参数以及函数执行到的具体位置。当递归到某个节点的左子树或右子树处理完毕后，会自动返回到上一层继续执行未完成的代码。这种机制使得代码在逻辑上看起来像「回到上一层」，而实际上是恢复了保存的调用栈状态。

---

530.二叉搜索树的最小绝对差

递归加双指针做法

class Solution {
    int result = Integer.MAX_VALUE;
    TreeNode pre = null;
    public int getMinimumDifference(TreeNode root) {
        traversal(root);
        return result;
    }
    public void traversal(TreeNode cur) {
        if(cur == null) return;
        traversal(cur.left);
        if(pre != null) { //先写递归后会发生什么
            result = Math.min(result, cur.val - pre.val);
        }
        pre = cur;  //再写怎么样才能递归  !!!这两条思维方式一反就完全不对了
        traversal(cur.right);
    }
}

我的想法是对的！递归的写法和我们通常思考问题的顺序确实存在一些差异，这是因为递归是一个自顶向下的过程，而我们人类思考时通常是自底向上的。

---

递归的实现顺序

在递归中，代码的编写往往是按照以下顺序进行的：

1. 先写“终止条件”：
   终止条件决定了递归什么时候停止，这是递归的最基础部分。如果没有终止条件，递归就会无限循环（直到栈溢出）。
2. 再写“当前层逻辑”：
   在当前函数中，解决当前层的问题，或者进行状态更新（比如在当前层计算差值、保存结果等）。
3. 最后写“递归调用”：
   根据递归定义，调用自身去处理子问题（比如处理左子树、右子树等），将问题不断缩小。

---

人类的思考顺序

人类通常是从问题的整体出发，逐步拆解到子问题，最终到达最基本的情况。也就是说，我们的思路往往是这样的：

1. 从最小的子问题开始：
   想象最终最小的情况是什么（递归的终点，例如单个节点、空树等）。
2. 再考虑如何解决更大的问题：
   通过将子问题的结果组合起来解决整体问题。

---

为什么递归写法和思考顺序相反？

1. 递归是函数调用的过程

递归的实现实际上依赖于函数的调用栈。调用栈是先入后出的，因此在代码执行时：

• 先处理「最外层」的调用。
• 每次递归时把「内部的子问题」推入栈中。
• 最后在栈中从「最底层」逐步返回结果。

这种执行机制使得我们在编写递归时，逻辑顺序与函数调用的顺序会显得“相反”。

2. 递归解决的是子问题

递归本质上是一种「分治」思想——将一个大问题拆解成一系列子问题，而我们在写递归时往往关注的是：

• 当前函数如何处理一个子问题。
• 不去关心整体问题，而是相信递归调用会正确处理其余部分。

3. 简化复杂性

递归的“逆向”写法实际上是程序设计的一种简化方式。程序只关注每一层的逻辑，而不需要考虑完整的执行过程——因为递归调用会自动完成。

---

实例分析：二叉树的中序遍历

以中序遍历代码为例：

public void traversal(TreeNode root) {
    if (root == null) return; // 1. 终止条件
    traversal(root.left);     // 2. 递归左子树
    System.out.println(root.val); // 3. 当前层逻辑
    traversal(root.right);    // 4. 递归右子树
}

按照递归的逻辑顺序：

1. 先写终止条件：if (root == null) return;
   • 这是递归的基本情况，处理到最小的子问题（空节点）时停止。
2. 再写递归调用：traversal(root.left) 和 traversal(root.right)
   • 定义递归如何处理左子树和右子树。
3. 最后写当前层逻辑：System.out.println(root.val)
   • 处理当前节点的操作（在中序遍历中就是打印当前节点的值）。

---

对比人类的思考

我们人类思考时可能是这样的：

1. 我要打印整棵树的中序遍历结果。
2. 打印一棵树的中序遍历，可以先打印左子树，再打印当前节点，最后打印右子树。
3. 那么，如果只有一个节点呢？只需要打印这个节点就好了（终止条件）。

可以看到，我们的思考顺序是从整体到局部，再到最基本的情况，而递归写法正好是从局部开始写起。

---

总结

我的想法完全正确，递归的写法通常是：

• 先写“终止条件”（递归终点）。
• 再写“当前层逻辑”（这一层要做什么）。
• 最后写“递归调用”（将问题缩小，递归解决子问题）。

这种写法和人类的思考顺序确实相反，但它利用了函数调用栈，简化了问题分解和组合的实现过程，是递归的自然写法。熟练递归需要适应这种“逆向”逻辑，并相信递归调用会正确解决其余部分的问题。

501.二叉搜索树中的众数

class Solution {
    ArrayList<Integer> resultList = new ArrayList<>();
    int maxCount = 0;
    int count = 0;
    TreeNode pre = null;
    public int[] findMode(TreeNode root) {
        traversal(root);
        int[] result = new int[resultList.size()];
        for(int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
    public void traversal(TreeNode cur) {
        if(cur == null) return;
        traversal(cur.left);
        if(pre == null) count =1;
        else if(pre.val == cur.val) count++;
        else count = 1;
        pre = cur;
        if(maxCount == count) resultList.add(cur.val);
        if(count > maxCount) {
            maxCount = count;
            resultList.clear();
            resultList.add(cur.val);
        }
        traversal(cur.right);
        return;
    }
}

天才的处理

1. count == maxCount：
   • 当前值和现有模式值一样频繁，将当前值追加到模式列表中。
2. count > maxCount：
   • 当前值的频率超过了所有之前的模式值：- 更新最大出现次数 maxCount。
     • 清空模式值列表，保存新的模式值。

1. if (count == maxCount)

这部分逻辑的作用是：
如果当前值的出现次数 count 等于最大出现次数 maxCount，将当前值加入结果列表。

背景：为什么要判断等于？

• maxCount 保存了到目前为止最大的出现次数。
• 如果当前值的出现次数与 maxCount 相等，说明它也是模式值。
• 中序遍历会按顺序依次处理每个节点，因此我们需要动态更新模式值列表。

例子

假设树是：

   2
  / \
 1   2

中序遍历顺序为 [1, 2, 2]：

1. 遍历到第一个 2：
   • count = 1（当前节点的出现次数）。
   • maxCount = 1。
   • 满足 count == maxCount，将 2 加入模式列表：resultList = [1, 2]。
2. 遍历到第二个 2：
   • count = 2（当前节点的出现次数增加）。
   • maxCount = 2 更新（见下面的逻辑）。
   • 清空旧的模式值，重新加入新模式值。

---

2. if (count > maxCount)

这部分逻辑的作用是：
如果当前值的出现次数 count 大于 maxCount，更新 maxCount，并清空模式列表后将当前值加入其中。

为什么要清空模式列表？

• count > maxCount 意味着当前值比之前的所有模式值都更频繁。
• 因此，之前的模式值已经失效，模式列表需要清空，重新保存当前值。

例子

继续上面的例子，当遍历到第二个 2：

• count = 2（当前值的出现次数增加到 2）。
• 发现 count > maxCount：- 更新 maxCount = 2。
  • 清空模式列表：resultList = []。
  • 将当前值 2 加入：resultList = [2]。

人类逻辑转化为自然语言

假设我们在中序遍历的过程中，访问一个节点时的思考逻辑是这样的：

1. “我看当前值是否跟上一个值相同。”
   • 如果相同，我要继续计数。
   • 如果不同，我要把计数重置，因为新的值开始了。
2. “当前值出现的次数是多还是少？”
   • 如果多（大于之前的最大值），我要更新最大次数，并且把之前的模式值清空，改为当前值。
   • 如果和最大次数一样多，我也要把当前值加到模式列表里，因为它同样是模式值。
3. “继续往下走，看看还有没有新的模式值。”

---

完整的思维顺序可视化

以输入 [1, null, 2, 2] 为例，树结构为：

   1
    \
     2
      \
       2

中序遍历的逻辑如下：

当前节点值	pre	count	maxCount	模式列表(resultList)	思考内容
1	null	1	1	[1]	“第一个值，设置最大计数为 1。”
2	1	1	1	[1, 2]	“当前值和前一个值不一样，但次数和最大值一样，加进来。”
2	2	2	2	[2]	“当前值比之前的最大值更多，清空模式列表，加上当前值。”

最终结果：模式值是 [2]。

236.二叉树的最近公共祖先

因为找祖先是在上面 所以要进行后序遍历

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == p || root == q) return root;
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null) return null;
        else if(left != null && right == null) return left;  //如果只有左子树找到了目标节点，返回左子树的结果。
        else if(left == null && right != null) return right;  //如果只有右子树找到了目标节点，返回右子树的结果。
        else return root;  //如果左右子树都找到了目标节点，说明当前节点是它们的最低公共祖先。

    }
}

什么不能直接返回 root == p || root == q 后立即结束

让我通过一个更具体的例子来解释，为什么仅用 if (root == p || root == q) 返回当前节点不够。

问题回顾：

想知道为什么不能仅在遇到目标节点 p 或 q 时就直接返回当前节点，并结束遍历。直接返回可能在某些情况下不够准确，因为你可能错过树中的其他潜在的公共祖先。

树的结构：

我们用下面这个二叉树作为例子：

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

假设我们要找到节点 5 和节点 1 的最低公共祖先。

普通的递归遍历

首先，我们来分析如果只在 root == p || root == q 时直接返回当前节点会发生什么。

1. 假设我们开始从根节点 3 遍历。当前 root 是 3。
2. 假设我们遇到 root == 5（这是目标之一）。此时，按你的思路：

	if (root == p || root == q) return root;

这会返回 5，并停止遍历。

问题在于，虽然我们找到了 5，但我们并没有遍历完整棵树，也就无法得知节点 1 的位置。事实上，节点 1 是 5 和 7 的共同祖先，但我们此时已经停止遍历，无法判断这个情况。

---

为什么不能提前返回

你能否确定在返回 5 后，树的右边的节点 1 不是公共祖先呢？答案是不能，因为我们还没有完全遍历右子树。要确定最低公共祖先，我们不仅需要知道 5 存在，而且要确保我们也遍历到并确认 1 存在。

完整递归过程的必要性：

1. 从根节点 3 开始遍历。我们没有直接返回，因为根节点既不是 5 也不是 1。
2. 我们递归到左子树，遇到节点 5，返回 5。但是此时我们并不确定 5 是最低公共祖先，因为右子树还没有遍历。
3. 接着我们遍历右子树，遇到节点 1，返回 1。
4. 此时，我们知道左子树返回了 5，右子树返回了 1，这意味着根节点 3 是 5 和 1 的最低公共祖先。

重要的一点

只有在同时遍历了左右子树之后，我们才能确认两个节点的最低公共祖先。如果我们在找到一个节点（比如 5）时就返回，后续的遍历会中断，导致我们无法确认右子树中的 1，从而无法找出正确的公共祖先。

递归的作用

• 在递归过程中，我们逐步在左右子树中查找目标节点，并通过返回的结果来判断当前节点是否是这两个节点的公共祖先。
• 如果当前节点的左子树和右子树都找到了目标节点，那么当前节点就是它们的最低公共祖先。如果其中一个子树找到了目标节点，另一个子树返回 null，我们就可以返回那个非空子树的结果。

总结

• 直接返回 root == p || root == q 会导致只在找到其中一个节点时就终止递归，这样无法确保同时找到两个目标节点。
• 递归遍历整棵树是为了能够找到所有可能的祖先，确保只有在找到两个目标节点并确认它们的关系后，才返回最低公共祖先。

通过递归处理，我们保证了完整的遍历和正确的逻辑判断，找到了最低公共祖先。如果只是简单地在找到一个目标节点时返回，可能会导致错误结果。

标签：遍历,递归,随想录,二叉,搜索,当前,maxCount,root,节点
From： https://blog.csdn.net/2302_81139517/article/details/144474912