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

Question

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

c++algorithmperformanceoptimizationbinary-search-tree

4

我编写了以下函数，用于查找二叉搜索树中任意路径的最小和：

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 属性？还有其他优化方法吗？

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

- user6490375

1

@user3112926，我完全同意您的观点，但我正在寻求算法改进。 - user6490375

1

我不知道为什么我看不到函数返回除零以外的任何东西。 - A.S.H

1

作为一个不错的代码改进：由于您已经检查了root是否为NULL，因此您可以省略其他级别的空值检查，并仅使用在left或right中的NULL调用minSumPath。 - Nobody moving away from SE

1

是的，但在下一次递归步骤中，root->left和root->right将成为新的root，再次检查是否为NULL。 - Nobody moving away from SE

1

这个问题很有趣。一定有一些方法可以利用二叉搜索树的结构。 - A.S.H

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- skypjack · Accepted Answer

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

例如：

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上查看两种方法的比较。
正如您所看到的，第二个函数根本不会探索不太可能的树。