在BST中打印第k個最小，難以遞歸

Question

我目前使用下面的代碼來執行BST的inorder遍歷。我的問題是，一旦達到第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。

Answer 1

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

其實，你不應該達到那個狀態。

由於您的函數似乎打算返回一個節點，因此如果計數較小，您要做的是返回NULL。

如果計數相等，您將返回當前節點。如果一個遞歸返回一個非NULL值，你會立即返回相同的值。