如何修正二叉搜索树中查找大于等于目标节点最小节点的函数

你的问题出在没有保留当前节点作为候选结果：当遇到比目标大的节点时，直接递归左子树，但左子树可能不存在符合条件的节点（比如示例中13的左子树11小于12，递归右子树得到NULL），此时原本的13才是符合要求的最小节点，却被丢弃了。

修改思路 #

• 当当前节点 n 大于目标节点时：
  1. 先递归遍历左子树，尝试找到更小的、且大于等于目标的节点
  2. 如果左子树返回有效节点，就用这个结果；如果左子树返回NULL，说明当前节点就是符合条件的最小节点，返回当前节点
• 当当前节点 n 小于等于目标节点时：
  • 直接递归遍历右子树，因为当前节点不符合要求，只有右子树可能存在更大的、符合条件的节点
• 当节点为NULL时，返回NULL

修正后的伪代码 #

// searches for the smallest node greater than or equal to a given node
static Node doTreeNext(Tree t, Node n, Node target) {
    // no node available
    if (n == NULL) {
        return NULL;
    }

    if (n > target) {
        // 先去左子树找更小的符合条件的节点
        Node leftResult = doTreeNext(t, n->left, target);
        // 如果左子树找到结果就用它，否则当前节点就是符合条件的最小节点
        return leftResult != NULL ? leftResult : n;
    } else { // n <= target
        // 当前节点不符合，去右子树找更大的节点
        return doTreeNext(t, n->right, target);
    }
}

示例验证（目标节点为12） #

1. 从根节点13开始，13>12，递归左子树11
2. 节点11<=12，递归右子树（NULL），返回NULL
3. 回到节点13的递归逻辑，左子树返回NULL，所以返回节点13，符合预期

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