19083 二叉树的最长路径_C

19083 二叉树的最长路径

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题语言: 不限定

Description

二叉树中，任意两个节点间都存在一条唯一的路径，请求出所有路径中最长的路径长度。

输入格式

第一行为一个整数n，表示结点个数，结点以数字编号，根节点为1。

n<10 第二行为一个数字和#号组成的字符串，采用完全二叉树的存储形式，#表示空树。

输出格式

输出所有路径中最长的路径长度

输入样例

5
1234##5

输出样例

提示

样例最长路径为（4,5），路径长度为4

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int a[1005][3];
int index_s = 1;
int max_L = 0;
void creat(string s)
{
    listL;
    L.push_back(1);
    while (L.size())
    {
        int k = L.size();
        while (k)
        {
            int i = L.front();
            L.pop_front();
            if (s[index_s] != '#')
            {
                a[i][1] = s[index_s]-'0';
                L.push_back(a[i][1]);
            }
            else
            {
                a[i][1] = 0;
                L.push_back(a[i][1]);
            }
            index_s++;
            if (index_s == s.length()) return;
            if (s[index_s] != '#')
            {
                a[i][2] = s[index_s] - '0';
                L.push_back(a[i][2]);
            }
            else
            {
                a[i][2] = 0;
                L.push_back(a[i][2]);
            }
            index_s++;
            if (index_s == s.length()) return;
        }
    }
}
int dfs(int i)
{
    if (i)
    {
        int left = dfs(a[i][1]);
        int right = dfs(a[i][2]);
        int len = max(left, right) + 1;
        max_L = max(max_L, left + right);
        return len;
    }
    return 0;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    int n = 0;
    cin >> n;
    if (!n)
    {
        cout << "0";
        return 1;
    }
    //getchar();
    string s;
    cin >> s;
    creat(s);
    dfs(1);
    cout << max_L;
}

改良：

#include //ASI
using namespace std;
int n,ans=0;
string s;
int dfs(int r)
{
    if(s[r-1]=='#'||r>s.size())/**< 空树，高度0 */
        return 0;
    int lhigh=dfs(2*r),rhigh=dfs(2*r+1);
    ans=max(ans,lhigh+rhigh);/**< 此题目是枚举公共祖先，以r为公共祖先的最大距离为两子树高度和 */
    return max(lhigh,rhigh)+1;/**< 返回树r高度 */
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n>>s;
    dfs(1);
    cout<

 
  
 					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/langs/674903.html

19083 二叉树的最长路径

发表评论

评论列表（0条）