재사용이 어려울 때 BST에서 k 번째로 작은 문자 인쇄

Question

현재 BST의 inorder 순회 수행을 위해 follow 코드를 사용하고 있습니다. 내 문제는 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; 
}   
*/ 

kth가 가장 작 으면 어떻게 멈출 수 있습니까? 현재이 기능은 전체 BST를 통해 계속됩니다.

Answer 1

반송 인 경우 self::$counter > $k.

사실, 당신은 그 상태에 있어서는 안됩니다.

함수가 노드를 반환하려고 한 것처럼 보였으 므로 카운트가 더 작 으면 NULL을 반환합니다.

개수가 같으면 현재 노드를 반환합니다. 재귀가 NULL이 아닌 값을 반환하면 즉시 동일한 값을 반환합니다.