0

我目前正在使用以下代码按顺序遍历 BST。我的问题是,一旦达到第 k 个最小值,所有计算就会停止。

http://codepad.viper-7.com/XMGcxz

我的问题是以下功能

public function _kthSmallest($node, $k){        

    if($node->left != NULL){
        $this->_kthSmallest($node->left, $k);
    }        
    echo $node->data . ' ';
    self::$counter++;
    echo self::$counter . "<br/>";

    /*
    if(self::$counter >= $k){
        return $node->data;
    }        
    */    

    if($node->right != NULL){

        $this->_kthSmallest($node->right, $k);
    }        
}

如果我取消注释此代码,我会遇到问题,因为根节点总是被打印出来。

/*
if(self::$counter >= $k){
    return $node->data;
}        
*/

关于在我达到第 k 个最小值后如何停止的任何想法?目前,该功能在整个 BST 中继续。

4

1 回答 1

1

如果返回self::$counter > $k

实际上,你不应该达到那种状态。

由于您的函数似乎打算返回一个节点,因此如果计数较小,您将返回 NULL。

如果计数相等,您将返回当前节点。如果递归返回非 NULL,您将立即返回相同的值。

于 2013-01-21T02:21:34.773 回答