二叉树两个节点的最大路径

参考博客：传送门

问题：如何求二叉树两个节点的最大路径

思路：分为两种情况
1）路径经过根节点
2）路径不经过根节点，是其左右子树的最大路径

比较这两种情况，去较大的即为最后结果

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 struct Node{
 6     Node *Left;
 7     Node *Right;
 8 };
 9 struct Result{
10     int maxdepth;
11     int maxDistance;
12 };
13 Result GetMaxDistance(Node *root){
14     if(!root){
15         Result ans={0,0};
16         return ans;
17     }
18     Result lans = GetMaxDistance(root->Left);
19     Result rans = GetMaxDistance(root->Right);
20     Result result;
21     result.maxdepth = max(lans.maxdepth,rans.maxdepth)+1;
22     result.maxDistance = max(max(lans.maxDistance,rans.maxDistance),lans.maxdepth+rans.maxdepth);
23     return result;
24 }
25 void Link(Node *nodes,int p,int l,int r){
26     if(l!=-1){
27         nodes[p].Left = &nodes[l];
28     }
29     if(r!=-1){
30         nodes[p].Right = &nodes[r];
31     }
32 }
33 int main()
34 {
35     Node test1[9] = { 0 };
36     Link(test1, 0, 1, 2);
37     Link(test1, 1, 3, 4);
38     Link(test1, 2, 5, 6);
39     Link(test1, 3, 7, -1);
40     Link(test1, 5, -1, 8);
41     cout<<"test1:"<<GetMaxDistance(&test1[0]).maxDistance<<endl;
42 
43     Node test2[4] = { 0 };
44     Link(test2, 0, 1, 2);
45     Link(test2, 1, 3, -1);
46     cout<<"test2:"<<GetMaxDistance(&test2[0]).maxDistance<<endl;
47 
48     Node test3[9] = { 0 };
49     Link(test3, 0, -1, 1);
50     Link(test3, 1, 2, 3);
51     Link(test3, 2, 4, -1);
52     Link(test3, 3, 5, 6);
53     Link(test3, 4, 7, -1);
54     Link(test3, 5, -1, 8);
55     cout<<"test3:"<<GetMaxDistance(&test3[0]).maxDistance<<endl;
56 
57     Node test4[9] = { 0 };
58     Link(test4, 0, 1, 2);
59     Link(test4, 1, 3, 4);
60     Link(test4, 3, 5, 6);
61     Link(test4, 5, 7, -1);
62     Link(test4, 6, -1, 8);
63     cout<<"test4:"<<GetMaxDistance(&test4[0]).maxDistance<<endl;
64     return 0;
65 }