DS树--二叉树之最大路径

题目描述

给定一颗二叉树的逻辑结构（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构

二叉树的每个结点都有一个权值，从根结点到每个叶子结点将形成一条路径，每条路径的权值等于路径上所有结点的权值和。编程求出二叉树的最大路径权值。如下图所示，共有4个叶子即有4条路径，

路径1权值=5 + 4 + 11 + 7 = 27路径2权值=5 + 4 + 11 + 2 = 22

路径3权值=5 + 8 + 13 = 26路径4权值=5 + 8 + 4 + 1 = 18

可计算出最大路径权值是27。

该树输入的先序遍历结果为ABCD00E000FG00H0I00，各结点权值为：

A-5，B-4，C-11，D-7，E-2，F-8，G-13，H-4，I-1

输入

输出

每行输出每棵二叉树的最大路径权值，如果最大路径权值有重复，只输出1个

输入样例1

2
AB0C00D00
4 5 3 2 6
ABCD00E000FG00H0I00
9 5 4 11 7 2 8 13 4 1
输出样例1

11
27

AC代码

#include "bits/stdc++.h"
using namespace std;

// 定义树节点结构体
struct TreeNode
{
    char val;
    int weight;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char x, int w) : val(x), weight(w), left(nullptr), right(nullptr) {}
};

// 用先序遍历字符串构建二叉树
TreeNode *buildTree(const string &preorder, int &index, unordered_map<char, int> &weights)
{
    if (index >= preorder.length() || preorder[index] == '0')
    {
        index++; // 空节点
        return nullptr;
    }
    char node_val = preorder[index++];
    TreeNode *node = new TreeNode(node_val, weights[node_val]);
    node->left = buildTree(preorder, index, weights);
    node->right = buildTree(preorder, index, weights);
    return node;
}
// 计算最大路径权值
int maxPathSum(TreeNode *root)
{
    if (!root)
        return 0;
    // 如果是叶子节点，返回当前节点的权值
    if (!root->left && !root->right)
        return root->weight;
    // 递归计算左右子树的最大路径权值
    int left_sum = root->left ? maxPathSum(root->left) : 0;
    int right_sum = root->right ? maxPathSum(root->right) : 0;

    // 返回当前节点权值加上左右子树中较大的路径权值
    return root->weight + max(left_sum, right_sum);
}

int main()
{
    int t;
    cin >> t; // 测试数据数量

    while (t--)
    {
        string preorder;
        cin >> preorder; // 输入先序遍历字符串
        int n;
        cin >> n; // 输入结点数量
        vector<char> daxie;
        for (int i = 0; i < preorder.length(); i++)
        {
            if (preorder[i] >= 'A' && preorder[i] <= 'Z')
            {
                daxie.push_back(preorder[i]);
            }
        }
        unordered_map<char, int> weights; // 结点权值映射
        // vector<char> nodes;
        int weight1;
        for (int i = 0; i < n; i++)
        {
            cin >> weight1;
            weights[daxie[i]] = weight1;
            // char node;
            // int weight;
            //  cin >> node >> weight;
            // weights[node] = weight;
            // nodes.push_back(node);
        }

        int index = 0;
        TreeNode *root = buildTree(preorder, index, weights); // 构建二叉树

        // 计算最大路径权值
        int max_path_sum = maxPathSum(root);
        cout << max_path_sum << endl; // 输出最大路径权值
    }

    return 0;
}

原文地址：https://blog.csdn.net/zgy11026/article/details/143593325

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！