在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值，你会立即返回相同的值。