如何获得二叉树中的最大路径成本

Question

如何获得二叉树中的最大路径成本，并打印一个包含所有路径数据元素的向量？

我知道如何获取成本但不知道如何获取元素向量有帮助吗？

struct Node
{
    int data;
    Node* left;
    Node* right;
};   

int treeMaxPath(Node* root) {
    if (root== NULL)
        return 0;
    else
        return root->data + max(treeMaxPath(root->left), treeMaxPath(root->right));
 }

Answer 1

Return 成本和路径的 pair。路径可以存放在vector<Node*>.

Answer 2

为整棵树完成对 treeMaxPath 的调用后（如果您在根上调用它，则应该为整棵树完成递归调用），您将使用它们的深度值更新整棵树。

现在您可以使用简单的循环轻松地进行小型跟踪，从树的根部沿着最高深度值遍历，直到遇到 NULL 子节点。

p.s. 我不确定您对 treeMaxPath 的实现是否正确。如果你在某个节点存储的数据是深度的，你的算法的某些部分应该改变。

Answer 3

自下而上处理树，存储data += max subtrees。
从顶部开始打印现在的值 (data - max subtrees) 然后打印最大值 child.
自上而下恢复数据值，data -= max subtrees。

备注：

这是 O(N) 的时间复杂度和 O(1) 的内存。可以通过向 Node 添加新变量来更改为存储最大值而不修改数据。它可以很容易地修改为打印树中的所有最大路径。

int maxChild(const Node *root) {
   return max(root->left ? root->left.data : 0,
              root->right ? root->right.data : 0);
}

void treeBottomUp(Node* root) {
    if (root) {
       treeBottomUp(root->left);
       treeBottomUp(root->right);
       root->data += maxChild(root);
    }
}

void treeRestore(Node *root) {
   if (root) {
      root->data -= maxChild(root);
      treeRestore(root->left);
      treeRestore(root->right);
   }
}

void printMaxPath(const Node* root) {
   if (root) {
     printf("%d\n", root->data - maxChild(root));
     if (root->left && root->left.data >= maxChild(root)) {
        printMaxPath(root->left);
     } else {
        printMaxPath(root->right);
     }
   }
}

并做到这一切：

void solveTree(Node *root) {
   treeBottomUp(root);
   printMaxPath(root);
   treeRestore(root);
}

如何获得二叉树中的最大路径成本

how to get the max path cost in binary tree

c++

visual-c++