在二叉搜索树中查找最小和的算法改进

我编写了以下函数来找出二叉搜索树中任何路径的最小总和：

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 财产？另外，我的方法中还可以使用其他优化吗？

注意：编辑代码以解决错误；

在某些情况下，知情搜索可能会有所帮助。
在最坏的情况下，计算成本与您的算法完全相同。

举个例子：

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 http://melpon.org/wandbox/permlink/ecnBSzdD9BvDwlmL.
正如您所看到的，第二个函数不会探索所有没有希望的树。