PHPは二叉木の距離が最も長い二つのノード間の距離を計算する
9921 ワード
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