leetcode
leetcode 2951 ~ 3000
二叉搜索树中的中序后继

二叉搜索树中的中序后继

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 37 ms, 内存: 19.6 MB

/*
 * 思路：
 * 使用中序遍历收集所有节点，然后找到目标节点 p 的下一个节点。
 * 利用 Java Stream API 来实现。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        List<TreeNode> nodes = new ArrayList<>();
        inorderTraversal(root, nodes);
        return IntStream.range(0, nodes.size())
                .filter(i -> nodes.get(i).val > p.val)
                .mapToObj(nodes::get)
                .findFirst()
                .orElse(null);
    }

    private void inorderTraversal(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        inorderTraversal(node.left, nodes);
        nodes.add(node);
        inorderTraversal(node.right, nodes);
    }
}

解释

方法:

此题解通过利用二叉搜索树的性质来寻找中序后继。根据二叉搜索树的特性，左子树的所有节点值都小于根节点，而右子树的所有节点值都大于根节点。因此，如果当前节点的值小于等于目标节点p的值，那么中序后继应该在右子树中；如果当前节点的值大于p的值，当前节点可能是中序后继，但还需要继续探索其左子树以确认是否存在更小但大于p的值的节点。通过这样的方式，我们可以确保找到的后继是比p节点值大中最小的一个。

时间复杂度:

O(h)，其中 h 是树的高度。对于平衡的二叉搜索树，h=log(n)，而对于非平衡树，h可能接近n。

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中，如果节点p是树中的最大值，你是如何处理这种情况的，以确保返回值为null？
▷
在算法实现中，当我们寻找中序后继时，如果节点p是树中的最大值，那么它的中序后继将不存在。该算法通过不断向右子树移动，直到无法继续移动（即`root`变为`None`）来处理这种情况。当我们遍历到最右边的节点（即最大值），并尝试访问其右子树时，由于右子树不存在，`root`将会变为`None`。在这种情况下，由于没有更新`ans`变量（因为没有找到更大的值），最终函数会返回`None`，符合题目要求的输出。
🦆
为什么在寻找中序后继时，当当前节点值大于p的值时，选择向左子树移动而不是右子树？
▷
在中序遍历的过程中，任何节点的中序后继是比该节点值大的最小节点。因此，当当前节点的值大于目标节点p的值时，当前节点可能是一个合适的后继候选。然而，我们需要确定是否存在一个更小但仍然大于p的值的节点作为更适合的后继。这样的节点，如果存在，一定位于当前节点的左子树中，因为左子树中的所有节点都小于当前节点（但有可能大于p）。继续探索左子树可以帮助我们找到这样的节点，如果直接移动到右子树，可能会错过更合适的中序后继。
🦆
如果树结构发生改变（例如添加或删除节点），在不重新构建整个树的情况下，这种方法是否仍然有效？
▷
如果树结构发生改变，例如添加或删除节点，而树本身维持了二叉搜索树的属性，那么本算法依然有效。算法的正确性基于二叉搜索树的性质，即左子树中所有的值都小于根节点，右子树所有的值都大于根节点，以及中序遍历二叉搜索树会得到一个递增序列。只要这些性质被保持，即使树的具体结构变化了，算法仍然能正确地找到中序后继。然而，如果树的修改破坏了二叉搜索树的性质（例如，插入或删除后没有适当的重新平衡），则可能需要额外的操作来恢复或验证这些性质以保证算法的正确执行。

相关问题

火星词典序列重建