leetcode
leetcode 2801 ~ 2850
后继者

后继者

难度:

标签:

题目描述

Write an algorithm to find the "next" node (i.e., in-order successor) of a given node in a binary search tree.

Return null if there's no "next" node for the given node.

Example 1:

Input: root = [2,1,3], p = 1

  2
 / \
1   3

Output: 2

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

Output: null

代码结果

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

/*
 * 题目思路：
 * 在二叉搜索树（BST）中，寻找指定节点的中序后继。中序后继是中序遍历中跟随指定节点的下一个节点。
 * 1. 如果节点有右子树，则中序后继为右子树的最左子节点。
 * 2. 如果节点没有右子树，则从根节点开始寻找，找到的最后一个比节点大的父节点即为中序后继。
 */

import java.util.*;
import java.util.stream.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // 使用栈进行中序遍历
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        boolean found = false;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            if (found) return current;
            if (current == p) found = true;
            current = current.right;
        }
        return null;
    }
}

解释

方法:

此题解的思路基于二叉搜索树（BST）的中序遍历特性，即中序遍历会按照节点值的升序排列输出所有节点。根据题目要求，我们需要找到节点p的中序后继节点。解决方案分为两种情况：1. 如果节点p有右子节点，则p的后继节点是其右子树中的最左节点。2. 如果节点p没有右子节点，则向上寻找直到找到一个是其父节点的左子节点的节点，该父节点即为后继节点。如果一直向上回溯到根节点还没找到，那么该节点没有后继节点，返回null。

时间复杂度:

O(h)，h为树的高度

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在节点p有右子节点的情况下，p的后继节点是其右子树中的最左节点？
▷
在二叉搜索树（BST）中，中序遍历的顺序是左子节点、当前节点、右子节点。当一个节点p有右子节点时，按照中序遍历的规则，接下来访问的节点应该是其右子树中的节点。在p的右子树中，最左边的节点是最小的节点，也就是在中序遍历中紧随p之后的节点。因此，p的后继节点是其右子树中的最左节点。
🦆
当节点p没有右子节点时，算法是如何确定向上搜索的方向并找到第一个大于p.val的节点的？
▷
当节点p没有右子节点时，后继节点在上面的结构中。我们从树的根节点开始，向下搜索定位到节点p。在这个过程中，如果当前节点的值大于p的值，则有可能是p的后继节点，我们暂时记录这个节点，并继续向左子树搜索，因为我们需要找到比p大的最小节点。如果当前节点的值小于或等于p的值，则向右子树搜索。这个搜索过程中记录的最后一个值大于p的节点就是p的后继节点。
🦆
如果节点p是树中的最大节点，算法是如何处理并返回null的？请解释其中的逻辑。
▷
如果节点p是树中的最大节点，那么它没有右子节点，且在向上回溯寻找后继节点的过程中，不会找到一个值大于p的节点。在这种情况下，由于树中没有节点的值大于p的值，我们在搜索过程中记录的后继节点（successor）将始终为null。最终，算法返回null，表示p没有后继节点。

相关问题

合法二叉搜索树首个共同祖先