时间戳

首页 > 解决方案 > 如何在 O(n) 中找到二叉搜索树的最大和路径中的最低键？

c - 如何在 O(n) 中找到二叉搜索树的最大和路径中的最低键？

问题描述

我已经在计算最大路径总和，但我想弄清楚哪个是路径内的最低键。我应该如何获得这些信息？我遇到了麻烦，因为如果我检查最大路径总和中的最小值，我不会得到我正在寻找的东西（当然）因为我首先重复到 BST 中的最低元素。在我尝试过的下面：

int Max_Path_Sum(struct node* root){
    int res= INT_MIN;   
    int min = INT_MAX;
    Max_Path_Sum_Util( root, &res, &min);
    printf("%d\n\n%d", min,res);    
    return res;
}


int Max_Path_Sum_Util(struct node* root, int *res, int *min){
    if(root == NULL) return  0;
    if( root->left == NULL && root->right == NULL)return root->key;

    int ls = Max_Path_Sum_Util(root->left ,res , min);
    int rs = Max_Path_Sum_Util(root->right ,res , min);

    if(root->left != NULL && root->right != NULL){
        *res = max(*res , ls + rs + root->key);
        return max(ls,rs)+ root->key;
    }   
    int sum = (root->left == NULL) ? rs+root->key : ls+root->key;
    if(root != NULL && *min> root->key)*min = root->key;
    return sum;
}

我收到了 BST 中最低的键，但我理解为什么它不是真正的结果，除了一些罕见的情况。我的 BST 不平衡（它只是一个家庭作业）所以在不关心平衡的情况下插入键。

struct node *root=New_Node(4);
Insert(root, 2);  
Insert(root, 1);  
Insert(root, 3);  
Insert(root, 6);  
Insert(root, 5); 
Insert(root, 4);
Insert(root, -5);
Insert(root,0);
Insert( root, 3);
Insert(root, 2);

使用这棵树，最大路径和的结果是 24，应该是正确的。至少我收到 6，这不是正确的答案。我觉得应该是2。

标签： cbinary-search-tree

解决方案

我遇到了麻烦，因为如果我检查最大路径总和中的最小值，我不会得到我正在寻找的东西（当然）因为我首先重复到 BST 中的最低元素。

我会以不同的方式描述这个问题：你不能直接记录路径上的最小节点，因为你不知道在递归函数的任何特定执行期间它是否在一个节点上运行，而这个节点最终会在最大路径上. 但是这个真正的问题只对某些实现提出了实际问题。

当通过一次只处理一个节点的算法搜索树中的路径时，在处理每个节点时通常需要考虑两种情况：

  • 感兴趣的路径通过当前节点，或
  • 它没有

具体算法通常会进一步细分。特别是，您处理从所选根节点到叶节点的树的递归方法需要考虑以下更具体的情况：

  • 路径从其父节点穿过当前节点（在此节点结束或继续通过其子节点之一）
  • 路径通过此节点且不包含其父节点（它也可能通过其一个或两个子节点）
  • 路径不经过该节点，但包含在以该节点为根的子树中
  • 路径不经过以当前节点为根的子树中的任何节点

在递归遍历期间处理给定节点时，您需要提供一个答案，就好像该节点是树的根一样（因为它可能是），如果不是，还需要提供足够的信息来正确确定答案。

现在请注意，树T 1中的最大路径总和和沿着该最大路径的最小元素都不会直接告知计算包含T 1作为子树的较大树T 2的那些属性。您不能只添加节点左右子树的最大路径总和 - 只有在每个子树中，最大路径从子树根开始的情况下才能给出正确答案，这样您就可以通过它们将它们连接在一起共同的父母形成一条路径。如果其中一个子树中的最大路径不包含子树根或子树根位于最大路径的中间某处，则无法通过将父节点连接到路径来形成路径。

因此，您需要关于每个子树的单独信息集：

  • 关于该子树内的一般最大和路径的信息，以及
  • 关于其中从子树根开始的最大和路径的信息（即使常见的是，它的路径和小于子树中的最大值）

在处理一个节点时，您可以结合后面的关于以它的子节点为根的子树的信息集来计算正在考虑的节点的两组信息。此外，您需要保持数据分离，以便在处理另一个节点的子树时，应用到其中一个节点的信息不会丢失。那看起来像什么？

我们先介绍另一种数据结构，以便于跟踪：

struct path_info {
    int sum;
    int min_value;
};

现在让我们考虑一下递归函数的签名需要是什么样子。有几种方法可以做到，但我会建议这样做：

struct path_info compute_max_path(struct node *root, struct path_info *max_leg)

max_leg返回值传达以指定节点为根的树的结果，并且通过输出参数传达为更大的树构建这样的结果所需的信息。

我不打算为您编写完整的解决方案，但我怀疑您还缺少一个想法：如何分离max_leg子树的结果。这里的关键是，当您递归时，您不会将max_leg参数转发给递归调用。相反，您声明新对象，并将指针传递给这些对象：

struct path_info left_leg;
struct path_info left_result = compute_max_path(root->left, &left_leg);
struct path_info right_leg;
struct path_info right result = compute_max_path(root->right, &right_leg);

然后，您就拥有了max_leg为当前节点设置数据以及计算和返回其子树的最大路径信息所需的所有信息。

推荐阅读