面试题 04.06. 后继者java

### Java 面试题：二叉树节点的后继者实现方法与解析

在Java中，对于二叉搜索树（BST），找到给定节点的后继者是一个常见的面试题目。这个问题不仅考察了对数据结构的理解，还测试了编程技巧。

#### 定义
在一个二叉搜索树中，如果所有左子树上的节点都小于根节点，而右子树上所有的节点都大于根节点，则该树被称为二叉搜索树。对于任意节点N来说：

- 如果存在右孩子，则其后继为右子树中最左边的那个节点；
- 若无右孩子且不是最右边的孩子，则沿着父指针向上直到遇到一个作为左孩子的祖先A；此时A即为其后继[^1]。

#### 实现思路
为了寻找指定节点p的后继者，可以按照如下逻辑编写算法：
- 当前节点有右子树时，在此情况下只需返回右子树里最小的关键字即可。
- 节点没有右子树的情况下，需要回溯到最近的一个祖先q处使得当前节点位于q左侧，那么这个q就是所求得后继者。

下面是具体的代码实现方式之一:

public class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int item){
        this.val = item;
        left = null;
        right = null;
    }
}

// 寻找给定节点 p 的后继者的方法
public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null || p == null) return null;

    // 存储路径以便于后续处理
    Stack<TreeNode> stack = new Stack<>();
    
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        
        // 找到了目标节点之后立即停止遍历并返回下一个访问的结点
        if (p == root && !stack.empty()) 
            return stack.peek();

        root = root.right;
    }

    return null;  // 没有发现匹配项则返回null表示不存在这样的后继者
}

上述代码通过迭代的方式实现了中序遍历来定位后继者的位置，并利用栈来保存从根到达特定位置所需经过的所有节点的信息。当找到了待查询的目标节点`p`以后就不再继续向下探索而是直接返回堆顶元素作为它的后继者[^2]。