PHP 计算二叉树距离最长的两个节点间的距离

 1 <?php
 2     #查找二叉树距离最长的两个节点的距离，即相距边数最多的两个节点的边数
 3     #解题思路：距离最长的两个节点有以下3中情况
 4     #1.两个节点一个位于左子树，一个位于右子树，则最长距离是左右子树的深度相加
 5     #2.两个节点都位于左子树，则最长距离是以左子树为根节点的左子树的两个左右子树的深度相加
 6     #3.两个节点都位于右子树，则最长距离是以右子树为根节点的右子树的两个左右子树的深度相加
 7 
 8     class Node {
 9         public $data = null;
10         public $left = null;
11         public $right = null;
12         public $parent = null;
13     }
14 
15     function get_max_long($root, &$depth) {
16         #此处结合二叉树的深度计算
17         if ($root == null) {
18             $depth = 0;
19             return 0;
20         }
21         #计算左右子树的最长距离，同时计算左右子树深度
22         $left_max = get_max_long($root->left, $ld);
23         $right_max = get_max_long($root->right, $rd);
24         $depth = max($ld, $rd) + 1;
25 
26         // echo "{$ld}|{$rd}|{$left_max}|{$right_max}<br>";
27         return max($ld + $rd, max($left_max, $right_max));
28     }
29 
30     #二叉树深度算法
31     #此处不用
32     function get_depth($root) {
33         if (!$root) {
34             return 0;
35         }
36 
37         $ld = get_depth($root->left) + 1;
38         $rd = get_depth($root->right) + 1;
39 
40         return max($ld, $rd);
41     }
42 
43     $root = new Node();
44     $n1 = new Node();
45     $n2 = new Node();
46     $n11 = new Node();
47     $n12 = new Node();
48     $n13 = new Node();
49     $n14 = new Node();
50     $n15 = new Node();
51     $n21 = new Node();
52 
53     $root->left = $n1;
54     $root->right = $n2;
55     $n1->left = $n11;
56     $n1->right = $n12;
57     $n11->left = $n13;
58     $n12->right = $n14;
59     $n13->left = $n15;
60     $n2->right = $n21;
61 
62     $max = get_max_long($root, $depth);
63     echo $max;
64 ?>
4 10 3 1 7 11 8 2