【数据结构】树--二叉树之最大路径

叶茂林

发布于 2023-07-30 13:11:12

2520

发布于 2023-07-30 13:11:12

文章被收录于专栏：叶子的开发者社区

题目描述

给定一颗二叉树的逻辑结构（先序遍历的结果，空树用字符‘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

输入

第一行输入一个整数t，表示有t个测试数据

第二行输入一棵二叉树的先序遍历，每个结点用字母表示

第三行先输入n表示二叉树的结点数量，然后输入每个结点的权值，权值顺序与前面结点输入顺序对应

以此类推输入下一棵二叉树

输出

每行输出每棵二叉树的最大路径权值，如果最大路径权值有重复，只输出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 <iostream>
#include <string>

using namespace std;

class BiTreeNode {
public:
    char data;                    //数据域
    int weight = 0;
    BiTreeNode *leftChild, *rightChild;    //左右子树指针
    BiTreeNode() : leftChild(NULL), rightChild(NULL) {}

    ~BiTreeNode() {}
};

class BiTree {
private:
    BiTreeNode *root;    //根结点指针
    string sTree;        //建树字符串
    int pos;            //标识建树字符串的当前字符位置
    BiTreeNode *CreateTree(int w=0);//建树私有函数
    int *weight;
public:
    int maxPath = 0;

    BiTree() : root(NULL) {};

    void Create(string vArray, int *weight);    //建树公有接口，参数是特定的先序遍历字符串
    void FindMaxPath(BiTreeNode *T) {
        if (T) {
            if (!T->leftChild && !T->rightChild) {
                if(T->weight>maxPath)
                    maxPath=T->weight;
            }
            FindMaxPath(T->leftChild);
            FindMaxPath(T->rightChild);
        }
    }

    void Show() {
        FindMaxPath(root);
        cout << maxPath << endl;
    }
};

void BiTree::Create(string vArray, int *weight) {
    this->weight=weight;
    pos = 0;
    sTree.assign(vArray);    //把参数保存到内部字符串
    root = CreateTree();    //建树成功后root指向根结点
}

BiTreeNode *BiTree::CreateTree(int w) {
    if (pos == sTree.size() || sTree[pos] == '0') {
        pos++;
        return NULL;
    }
    BiTreeNode *T = new BiTreeNode();
    T->weight = *(weight++)+w;
    T->data = sTree[pos++];
    T->leftChild = CreateTree(T->weight);
    T->rightChild = CreateTree(T->weight);
    return T;
}

int main() {
    int t, n;
    string temp;
    cin >> t;
    while (t--) {
        cin >> temp >> n;
        int weight[n];
        for (int i = 0; i < n; i++)
            cin >> weight[i];
        BiTree tree;
        tree.Create(temp, weight);
        tree.Show();
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树