улучшения алгоритмического для нахождения минимальной суммы в бинарном дереве поиска

Question

Я написал следующую функцию, чтобы выяснить минимальную сумму любого пути в бинарном дереве поиска:

int minSumPath(TreeNode* root) { 
    if(root==NULL) 
     return 0; 

    int sum = root->value; 
    if(root->left!=NULL && root->right!=NULL) 
     sum += min(minSumPath(root->left),minSumPath(root->right)); 
    else 
     if(root->left==NULL) 
      sum += minSumPath(root->right); 
     else 
      sum += minSumPath(root->left); 

    return sum; 
} 

Хотя приведенный выше код генерирует правильный вывод, Я чувствую, что не использую тот факт, что это двоичное дерево поиска (BST), а не только двоичное дерево.

В BST левый дочерний узел меньше корневого и правого узлов, поэтому логически мы можем рассматривать только левые дочерние узлы каждого корня; но что, если у BST есть только один ребенок справа (с значением 10) и несколько дочерних узлов слева (с суммой> 10)?

В этом случае минимальная сумма будет равна 10 (что находится справа).

Как я мог бы использовать свойство BST, если вообще? Кроме того, любые другие оптимизации, которые я могу использовать в моем подходе?

Примечание: Отредактировано код для устранения ошибки;

Answer 1

Информационный поиск может помочь в некоторых случаях.
В худшем случае вычислительная стоимость точно такая же, как и у вашего алгоритма.

В качестве примера:

int minSumPathOpt(TreeNode* root) { 
    if(root == nullptr) return 0; 

    int sum = -1; 

    std::stack<std::pair<TreeNode*, int>> todo; 
    todo.push(std::make_pair(root, 0)); 

    while(not todo.empty()) { 
     std::pair<TreeNode*, int> curr = todo.top(); 
     todo.pop(); 

     TreeNode *node = curr.first;   
     int part = curr.second + node->value; 

     if(sum == -1 || part < sum) { 
      if(!node->left && !node->right) { 
       sum = part; 
      } else { 
       if(node->right) todo.push(std::make_pair(node->right, part)); 
       if(node->left) todo.push(std::make_pair(node->left, part)); 
      } 
     } 
    } 

    return sum; 
} 

Основная идея заключается в том, чтобы отслеживать текущее минимальное время выполнения DFS. Это даст вам возможность обрезать все поддеревья всякий раз, когда сумма значений к их корню уже больше текущего минимума.
Кроме того, изучение левого дерева перед тем, как смотреть вправо, может помочь максимизировать результат (нет уверенности, но это хорошая идея из-за того, как определены BST).

См. Сравнение двух подходов на wandbox.
Как вы можете видеть, вторая функция не исследует на всех деревьях, которые не являются многообещающими.