在二叉搜索树中查找最小和的算法改进 [英] Algorithmic improvement for finding minimum sum in a Binary Search Tree

问题描述

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

I wrote the following function to find out the minimum sum of any path in a Binary Search Tree:

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)而不只是二进制树的事实.

While the above code generates the correct output, I feel that I am not leveraging the fact that it is a Binary Search Tree (BST) and not just a Binary Tree.

在BST中，左子节点小于根节点和右节点，因此从逻辑上讲，我们只能考虑每个根的左子节点；但是如果BST在右侧只有一个子节点(比如说值为10)，在左侧只有多个子节点(总和> 10)呢?

In a BST the left child node is smaller than the root and right node, so logically we can only consider the left child nodes of each root; but what if the BST has only a single child on the right (with say value 10) and multiple child nodes on the left (with sum >10)?

在这种情况下，最小总和为10(在右侧).

In this case the minimum sum would be 10 (which is on the right).

如果有的话，我将如何利用BST属性?另外，我可以在方法中使用其他优化方法吗?

How I would be able to leverage the BST property, if at all? Also, any other optimizations that I can use in my approach?

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

Note: Edited the code to resolve the error;

推荐答案

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

An informed search could help in some cases.
In the worst case, the computational cost is exactly the same of your algorithm.

例如:

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的定义，这是个好主意).

The basic idea is to track the current minimum while performing a DFS. This will give you the chance to prune entire subtrees whenever the sum of the values to their root are already greater than the current minimum.
Moreover, exploring the left tree before to look at the right one could help maximizing the result (no assurance indeed, but it's a good idea because of how BSTs are defined).

在 wandbox 上查看两种方法的比较.
如您所见，第二个功能不会在所有没有前途的树上探索.

See a comparison of the two approaches on wandbox.
As you can see, the second function doesn't explore at all trees that are not promising.

这篇关于在二叉搜索树中查找最小和的算法改进的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！