coding-questions/problem/Tree/Longest distance between two nodes.cpp at master · checkcheckzz/coding-questions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*

Longest distance between any two nodes in binary tree

*/

/*

solution: the longest distance should be in left subtree or in right subtree or it should pass through root.
We can do it recursively.
O(nlogn) time, O(1) space

*/


struct Node {

  int val
  Node *plft;
  TreeNode *prgt;

  Node(int v) : val(v), plft(NULL), prgt(NULL) {}

};

int Height(Node* root) {

       if (root == NULL) {
             return 0;
       }

       int leftheight = Height(root->plft);
       int rightheight = Height(root->prgt);

       if (leftheight > rightheight) {

           return leftheight + 1;

       } else {

           return rightheight + 1;
       }
}

int LongestDistanceTwoNodes(Node *root) {

       if (root == NULL) {

          return 0;
       }

       int lheight = Height(root->plft);
       int rheight = Height(root->prgt);

       int llength = LongestDistanceTwoNodes(root->plft);
       int rlength = LongestDistanceTwoNodes(root->prgt);

       return max(lheight + rheight+ 1, max(llength, rlength));
}