数组实现的二叉搜索树如何查找左子树最大值对应的索引

问题原因 #

你当前的findNew方法没有接收递归调用的返回值，导致深层递归查到的最大节点索引被丢弃，最终始终返回最开始传入的根节点索引，不符合预期。

修正后的findNew方法 #

//find largest node in left subtree and return its index
private int findNew(int index) {
    int r = right[index];
    if(r != -1) {
        // 直接返回递归调用的结果，把深层查到的最大索引向上传递
        return findNew(r);
    }
    // 没有右子节点时，当前节点就是左子树的最大值节点
    return index;
}

逻辑说明 #

找左子树最大值的核心逻辑是沿着左子树的右节点路径一直向下遍历，直到没有右子节点为止，该节点就是左子树的最大值节点：

• 若当前节点存在右子节点，最大值一定在右子树中，直接返回右子树的查找结果
• 若当前节点不存在右子节点，当前节点就是目标最大值节点，直接返回其索引

该实现完全符合你要求的无循环、非void返回值、递归实现的约束，和你现有代码结构完全兼容。

内容的提问来源于stack exchange，提问作者WeekendJedi