эффективно найти k-й наименьший элемент в дереве двоичного поиска? - PullRequest
Новая
       4

эффективно найти k-й наименьший элемент в дереве двоичного поиска?

0 голосов
/ 29 ноября 2018

Сегодня я столкнулся с вопросом об интервью ниже, и я нашел рекурсивное и итеративное решение, как упомянуто ниже, но каким-то образом интервьюер не был доволен.Я не уверен, почему.

Учитывая двоичное дерево поиска, найдите в нем k-й наименьший элемент.

Есть ли лучший способ решить эту проблему либо в рекурсивнойили итеративным способом? 

  /*****************************************************
   *
   * Kth Smallest Recursive
   *
   ******************************************************/
  public int kthSmallestRecursive(TreeNode root, int k) {
    int count = countNodes(root.left);
    if (k <= count) {
      return kthSmallestRecursive(root.left, k);
    } else if (k > count + 1) {
      return kthSmallestRecursive(root.right, k - 1 - count);
    }

    return root.data;
  }

  public int countNodes(TreeNode n) {
    if (n == null)
      return 0;

    return 1 + countNodes(n.left) + countNodes(n.right);
  }

  /*****************************************************
   *
   * Kth Smallest Iterative
   *
   ******************************************************/

  public int kthSmallestIterative(TreeNode root, int k) {
    Stack<TreeNode> st = new Stack<>();

    while (root != null) {
      st.push(root);
      root = root.left;
    }

    while (k != 0) {
      TreeNode n = st.pop();
      k--;
      if (k == 0)
        return n.data;
      TreeNode right = n.right;
      while (right != null) {
        st.push(right);
        right = right.left;
      }
    }

    return -1;
  }

Я упомянул сложность в обоих вышеупомянутых решениях как O (глубина узла), которая равна O (log n).

Мой итеративныйверсия занимает дополнительное место.Есть ли способ сделать это без лишних пробелов?

Ответы [ 2 ]

0 голосов
/ 29 ноября 2018 
 public int printInorder(Node node, int k) 
    { 
        if (node == null || k <= 0) //Stop traversing once you found the k-th smallest element
            return k; 

        /* first recur on left child */
        k = printInorder(node.left, k); 

        k--;
        if(k == 0) {  
            System.out.print(node.key);
        }

        /* now recur on right child */
        return printInorder(node.right, k);
    }

В методе countNodes() вашего рекурсивного подхода вы пересекаете дерево в каждом узле для подсчета.countNodes() операция - O (n), и вы выполняете операцию на log (n) количестве узлов.Таким образом, порядок сложности вашего рекурсивного решения равен O(n^2), тогда как упомянутый выше подход решается в O (n).

0 голосов
/ 29 ноября 2018

Во-первых, я сомневаюсь, что это займет O (logn).Это как минимум O (n) для ванильного дерева двоичного поиска.

Для vanilla bst вы можете делать итеративный или рекурсивный, оба моделируют один и тот же процесс обхода игнорирующего с наихудшей временной сложностью O (n) и пространственной сложностью O(logn) (обратите внимание, что даже рекурсивное решение может взять пространство O (logn) из стека).

Однако вы можете ускорить процесс или использовать меньше места, если немного измените структуру данных:

  1. Если вы используете бинарное дерево поиска, в котором каждый узел записывает количество общих узлов под ним, вы можете сделать это, как если бы это был отсортированный массив, и получить к k-му элементу с помощью O(logn) время и пространство O (1).

  2. Если вы используете бинарное дерево поиска, каждый узел которого содержит родительский указатель и индикатор состояния, вы можете пройти по дереву в одном и том жемода как ванильное решение.По пути вы отмечаете, является ли узел.не пройден 2. пройден ли его левый узел 3. пройден ли оба узла.тогда вы можете сделать это за O (n) время и O (1) пространство.

...