Как преобразовать алгоритм рекурсии «Сортированный массив в сбалансированный BST» в итеративный алгоритм?

This problem is mostly due to me not understanding the way the normal recursive method words, although when looking at them side by side to see how to approach it, I always get stuck on what to do.

Это требует практики ... и, возможно, анализа работ других людей.

require two stacks (to contain a left_Index and right_Index).

Приношу свои извинения, я не понимаю, почему ОП так думает. В моей демонстрации ниже есть только 1 стек под названием «todo», возможно, вы найдете эту идею полезной.

#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>

#include "./BTree.hh"  // code not provided, used in this MCVE to 
                       // conveniently provide "showTallTreeView()" 

typedef std::vector<int>  IVec_t;  

class T607_t
{
   IVec_t m_sortedIVec;    // sorted - created with for loop
   IVec_t m_recursiveIVec; // extract from sorted by recursion
   IVec_t m_iterativeIVec; // extract from sorted by iteration

public:

   T607_t() = default;
   ~T607_t() = default;

   int exec(int , char**  )
      {
         fillShowSortedIVec();

         fillShowRecursiveIVec();

         fillShowIterativeIVec();

         showResults();

         return 0;
      }

private: // methods

Векторы находятся в классе T607_t, поэтому каждый доступен для любой функции-члена.

Для этого MCVE я просто создаю «IVec_t m_sortedIVec;» и заполните простым циклом for:

   void fillShowSortedIVec()
      {
         for (int i=0; i<15; ++i)
            m_sortedIVec.push_back (i*100);  // create in sorted order

         showIVec(m_sortedIVec, "\n  m_sortedIVec   :");   
      }

Далее (в этом MCVE) идет рекурсивная заливка и отображение и моя адаптация рекурсивного метода OP для создания рекурсивной последовательности вставки:

   // ///////////////////////////////////////////////////////////////
   void fillShowRecursiveIVec()
      {
         assert(m_sortedIVec.size() > 0);
         int max = static_cast<int>(m_sortedIVec.size()) - 1;

         // use OP's recursive insert
         array2balancedR (m_sortedIVec, 0, max);  
         // NOTE - 'sequence' is inserted to 'm_recursiveIVec'
         //        instead of into tree the op did not share

         showIVec(m_recursiveIVec, "\n  m_recursiveIVec:");
      }

   // recursive extract from: m_sortedIVec  to: m_recursiveIVec
   // my adaptation of OP's recursive method
   void array2balancedR(IVec_t& array, int lIndex, int rIndex)
      {
         //base case
         if (lIndex > rIndex)
         {
            return;
         }
         else    //recursive calls
         {
            int mid = (lIndex+rIndex)/2;
            m_recursiveIVec.push_back(array[mid]);  // does this
            // tree.insert(array[mid]);             // instead of this

            array2balancedR(array, lIndex, mid-1);  // recurse left
            array2balancedR(array, mid+1, rIndex);  // recurse right
         }
      }

Примечание. Я оставил "IVec_t & array" в качестве параметра этой функции, потому что он есть в коде OP. Внутри этой оболочки класса функция не должна передавать массив «через рекурсию», потому что каждый метод имеет доступ к данным экземпляра.

Далее (в этом MCVE) выполняется действие заполнения и отображения с использованием одного возможного итеративного подхода. Я тщательно разработал этот итеративный подход, чтобы он соответствовал рекурсивным усилиям OP.

Во-первых, я добавил «инструмент» (IndxRng_t), чтобы упростить «стековый» захват итераций для последующей обработки. (т.е. «todo»).

   // //////////////////////////////////////////////////////////////
   // iterative extract from  m_sortedIVec  to: m_iterativeIVec
   class IndxRng_t  // tool to simplify iteration
   {
   public:
      IndxRng_t() = delete; // no default
      IndxRng_t(int li, int ri)
         : lIndx (li)
         , rIndx (ri)
         {}
      ~IndxRng_t() = default;

      // get'er and set'er free.  also glutton free.  gmo free.
      bool            done() { return (lIndx > rIndx); } // range used up
      int              mid() { return ((lIndx + rIndx) / 2); } // compute
      IndxRng_t   left(int m) { return {lIndx, m-1}; }  // ctor
      IndxRng_t  right(int m) { return {m+1, rIndx}; }  // ctor
   private:
      int lIndx;
      int rIndx;
   };


   void fillShowIterativeIVec()
      {
         assert(m_sortedIVec.size() > 0);
         int max = static_cast<int>(m_sortedIVec.size()) - 1;

         array2balancedI(m_sortedIVec, 0, max); 
         // 'sequence' inserted to 'm_iterativeIVec'

         showIVec(m_iterativeIVec, "\n  m_iterativeIVec:");
      }


   void array2balancedI(IVec_t& array, int lIndex, int rIndex)
      {
         std::vector<IndxRng_t>  todo;
         todo.push_back({lIndex, rIndex}); // load the first range

         // iterative loop (No recursion)
         do
         {
            if (0 == todo.size()) break; // exit constraint
            // no more ranges to extract mid from

            // fetch something to do
            IndxRng_t  todoRng = todo.back();
            todo.pop_back(); // and remove from the todo list

            if (todoRng.done()) continue; // lIndex > rIndex 

            int mid = todoRng.mid();
            m_iterativeIVec.push_back(array[mid]);  // do this
            // tree.insert(array[mid]);             // instead of this

            todo.push_back(todoRng.right(mid) ); // iterate on right
            todo.push_back(todoRng.left(mid)  ); // iterate on left

         }while(1);
      }

И этот mcve генерирует отображение результатов:

   void showResults()
      {
         assert(m_recursiveIVec.size() == m_sortedIVec.size());
         assert(m_iterativeIVec.size() == m_sortedIVec.size());

         std::cout << std::endl;

         std::stringstream ss; // for btree use only

         std::cout << "\n  demo:\n     create a BTree, "
                   << std::flush;
         std::cout << "\n     Insert IVec_t " << std::endl;

         BBT::BTree_t btree(ss);
         std::cout << std::flush;

         for (size_t i=0; i<m_iterativeIVec.size(); ++i)
            btree.insertPL(m_iterativeIVec[i]);

         std::cout << "\n iterative result:\n\n" 
                   << btree.showTallTreeView();
      }


   void showIVec(IVec_t& ivec, std::string lbl)
   {
      std::cout << lbl << std::endl;
      for (auto it : ivec)
         std::cout << std::setw(5) << it << std::flush;
      std::cout << std::endl;
   }

}; // class T607_t


int main(int argc, char* argv[])
{
   T607_t  t607;
   return  t607.exec(argc, argv);
}

Мой вывод (на Ubuntu 17.10, g ++ 7.2.0),

  m_sortedIVec   :
    0  100  200  300  400  500  600  700  800  900 1000 1100 1200 1300 1400

  m_recursiveIVec:
  700  300  100    0  200  500  400  600 1100  900  800 1000 1300 1200 1400

  m_iterativeIVec:
  700  300  100    0  200  500  400  600 1100  900  800 1000 1300 1200 1400


  demo:
     create a BTree, 
     Insert IVec_t 

 iterative result:

  BTree_t::showTallTreeView():  (balance: 0  sz: 15)

                     0 
               100 
                    200 
          300 
                    400 
               500 
                    600 
     700 
                    800 
               900 
                    1000 
          1100 
                    1200 
               1300 
                    1400 

-----------------

Итеративная реализация JavaScript для преобразования отсортированного массива в двоичное дерево поиска (BST):

function sortedArrayToBstIteratively(nums) {
    // use stack to iteratively split nums into node tuples and reuse values
    const stack = []

    // add root node to tree
    const tree = { first: 0, last: nums.length - 1 }
    stack.push(tree)

    // split array in the middle and continue with the two halfs
    while (stack.length > 0) {
        const node = stack.pop()

        if (node.last >= node.first) {
            if (node.last === node.first) {
                // node reaches a single leaf value (last == first)
                node.value = nums[node.first]
            } else {
                // node has still valid indices to further split the array (last > first)
                const middle = Math.ceil((node.first + node.last) / 2)
                node.value = nums[middle]
                node.left = { first: node.first, last: middle - 1 }
                node.right = { first: middle + 1, last: node.last }
                stack.push(node.left)
                stack.push(node.right)
            }
        } else {
            // node has no more valid indices (last < first), create empty leaf
            node.value = null
        }

        delete node.first
        delete node.last
    }

    // console.info(JSON.stringify(tree))

    return tree
}