二叉树的最长路径
19083
Description
二叉树中，任意两个节点间都存在一条唯一的路径，请求出所有路径中最长的路径长度。输入格式
第一行为一个整数n，表示结点个数，结点以数字编号，根节点为1。n<10 第二行为一个数字和#号组成的字符串，采用完全二叉树的存储形式，#表示空树。输出格式
输出所有路径中最长的路径长度输入样例
5 1234##5输出样例
4提示
样例最长路径为（4,5），路径长度为4
OJ标程真的666
#include using namespace std;
int n,ans=0;
string s;
int dfs(int root)
{if(s[root-1]=='#'||root>s.size()){return 0;}int lchild=dfs(2*root),rchild=dfs(2*root+1);ans=max(ans,lchild+rchild);return max(lchild,rchild)+1;
}
int main()
{cin>>n>>s;dfs(1);cout< 做这道题时，我就觉得似曾相识，恨自己怎么改了个名就不会做啦！！
这道题和求二叉树的直径简直是一猫一样，只是题设条件不大一样。
回顾下二叉树的直径吧：
Description
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。1/ \2 3/ \ 4 5 答案为3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
输入格式
共n行。 第一行一个整数n，表示有n个结点，编号为1至n。 第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子输出格式
输出二叉树的直径。输入样例
5 1 2 1 3 2 4 2 5输出样例
3
代码如下：
#include typedef long long ll;
using namespace std;
int n,child[105][3],ans=0;
int dfs(int root)
{if(!root)return 0;int lchild=dfs(child[root][1]),rchild=dfs(child[root][2]);int len=max(lchild,rchild)+1;ans=max(ans,lchild+rchild);return len;
}
int main()
{int i,j,x,y;cin>>n;for(i=1; i>x>>y;if(!child[x][1])child[x][1]=y;elsechild[x][2]=y;}dfs(1);cout<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！