Skip to content

Commit 22099af

Browse files
dairongpengdairongpeng
committed
refactor: tree max distance
1 parent 23dcdac commit 22099af

File tree

1 file changed

+43
-155
lines changed

1 file changed

+43
-155
lines changed

‎08-二叉树递归解题思路.md

Lines changed: 43 additions & 155 deletions
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@ func Process(node *Node) *BalanceInfo {
7777
}
7878
```
7979

80-
### .1.2 例二：返回二叉树任意两个节点最大值
80+
### 1.1.2 例二：返回二叉树任意两个节点最大值
8181

8282
给定一棵二叉树的头结点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离
8383

@@ -87,166 +87,54 @@ func Process(node *Node) *BalanceInfo {
8787
8888
> 结论：那么根据递归套路，我们每次递归，需要返回X左树的最大距离和高度，同理返回X右树的最大距离和高度。Info包含最大距离和高度
8989
90-
```Java
91-
package class08;
92-
93-
import java.util.ArrayList;
94-
import java.util.HashMap;
95-
import java.util.HashSet;
96-
97-
public class Code08_MaxDistance {
98-
99-
public static class Node {
100-
public int value;
101-
public Node left;
102-
public Node right;
103-
104-
public Node(int data) {
105-
this.value = data;
106-
}
107-
}
108-
109-
public static int maxDistance1(Node head) {
110-
if (head == null) {
111-
return 0;
112-
}
113-
ArrayList<Node> arr = getPrelist(head);
114-
HashMap<Node, Node> parentMap = getParentMap(head);
115-
int max = 0;
116-
for (int i = 0; i < arr.size(); i++) {
117-
for (int j = i; j < arr.size(); j++) {
118-
max = Math.max(max, distance(parentMap, arr.get(i), arr.get(j)));
119-
}
120-
}
121-
return max;
122-
}
123-
124-
public static ArrayList<Node> getPrelist(Node head) {
125-
ArrayList<Node> arr = new ArrayList<>();
126-
fillPrelist(head, arr);
127-
return arr;
128-
}
129-
130-
public static void fillPrelist(Node head, ArrayList<Node> arr) {
131-
if (head == null) {
132-
return;
133-
}
134-
arr.add(head);
135-
fillPrelist(head.left, arr);
136-
fillPrelist(head.right, arr);
137-
}
138-
139-
public static HashMap<Node, Node> getParentMap(Node head) {
140-
HashMap<Node, Node> map = new HashMap<>();
141-
map.put(head, null);
142-
fillParentMap(head, map);
143-
return map;
144-
}
145-
146-
public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
147-
if (head.left != null) {
148-
parentMap.put(head.left, head);
149-
fillParentMap(head.left, parentMap);
150-
}
151-
if (head.right != null) {
152-
parentMap.put(head.right, head);
153-
fillParentMap(head.right, parentMap);
154-
}
155-
}
156-
157-
public static int distance(HashMap<Node, Node> parentMap, Node o1, Node o2) {
158-
HashSet<Node> o1Set = new HashSet<>();
159-
Node cur = o1;
160-
o1Set.add(cur);
161-
while (parentMap.get(cur) != null) {
162-
cur = parentMap.get(cur);
163-
o1Set.add(cur);
164-
}
165-
cur = o2;
166-
while (!o1Set.contains(cur)) {
167-
cur = parentMap.get(cur);
168-
}
169-
Node lowestAncestor = cur;
170-
cur = o1;
171-
int distance1 = 1;
172-
while (cur != lowestAncestor) {
173-
cur = parentMap.get(cur);
174-
distance1++;
175-
}
176-
cur = o2;
177-
int distance2 = 1;
178-
while (cur != lowestAncestor) {
179-
cur = parentMap.get(cur);
180-
distance2++;
181-
}
182-
return distance1 + distance2 - 1;
183-
}
184-
185-
public static int maxDistance2(Node head) {
186-
return process(head).maxDistance;
187-
}
90+
```Go
91+
package main
18892

189-
// 我们的信息，整棵树的最大距离和整棵树的高度
190-
public static class Info {
191-
public int maxDistance;
192-
public int height;
93+
import "math"
19394

194-
public Info(int dis, int h) {
195-
maxDistance = dis;
196-
height = h;
197-
}
198-
}
199-
200-
// 以X节点为头
201-
public static Info process(Node X) {
202-
// base case
203-
if (X == null) {
204-
return new Info(0, 0);
205-
}
206-
// 默认从左树拿到我们需要的info
207-
Info leftInfo = process(X.left);
208-
// 默认从右树拿到我们需要的info
209-
Info rightInfo = process(X.right);
210-
// 用左右树的信息，加工自身的info
211-
// 自身的高度是，左右较大的高度加上自身节点高度1
212-
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
213-
// 自身最大距离，是左右树最大距离和左右树高度相加再加1，求最大值
214-
int maxDistance = Math.max(
215-
Math.max(leftInfo.maxDistance, rightInfo.maxDistance),
216-
leftInfo.height + rightInfo.height + 1);
217-
// 自身的info返回
218-
return new Info(maxDistance, height);
219-
}
95+
type Node struct {
96+
Val int
97+
Left *Node
98+
Right *Node
99+
}
220100

221-
// for test
222-
public static Node generateRandomBST(int maxLevel, int maxValue) {
223-
return generate(1, maxLevel, maxValue);
224-
}
101+
type DistanceInfo struct {
102+
// 当前节点为树根的情况下，该树的最大距离
103+
MaxDistance int
104+
// 当前节点为树根的情况下，该树的高度
105+
Height int
106+
}
225107

226-
// for test
227-
public static Node generate(int level, int maxLevel, int maxValue) {
228-
if (level > maxLevel || Math.random() < 0.5) {
229-
return null;
230-
}
231-
Node head = new Node((int) (Math.random() * maxValue));
232-
head.left = generate(level + 1, maxLevel, maxValue);
233-
head.right = generate(level + 1, maxLevel, maxValue);
234-
return head;
235-
}
108+
// GetMaxDistance 给定二叉树头节点，求该二叉树的最大距离
109+
func (head *Node) GetMaxDistance() int {
110+
return Process2(head).MaxDistance
111+
}
236112

237-
public static void main(String[] args) {
238-
int maxLevel = 4;
239-
int maxValue = 100;
240-
int testTimes = 1000000;
241-
for (int i = 0; i < testTimes; i++) {
242-
Node head = generateRandomBST(maxLevel, maxValue);
243-
if (maxDistance1(head) != maxDistance2(head)) {
244-
System.out.println("Oops!");
245-
}
246-
}
247-
System.out.println("finish!");
113+
func Process2(node *Node) *DistanceInfo {
114+
// base case
115+
if node == nil {
116+
return &DistanceInfo{
117+
MaxDistance: 0,
118+
Height: 0,
119+
}
120+
}
121+
122+
// 左树信息
123+
leftInfo := Process2(node.Left)
124+
// 右树信息
125+
rightInfo := Process2(node.Right)
126+
// 用左右树的信息，加工当前节点自身的info
127+
// 自身的高度是，左右较大的高度加上自身节点高度1
128+
curHeight := int(math.Max(float64(leftInfo.Height), float64(rightInfo.Height)))
129+
// 自身最大距离，(左右树最大距离)和(左右树高度相加再加1)，求最大值
130+
curMaxDistance := int(math.Max(
131+
math.Max(float64(leftInfo.MaxDistance), float64(rightInfo.MaxDistance)),
132+
float64(leftInfo.Height + rightInfo.Height + 1)))
133+
// 自身的info返回
134+
return &DistanceInfo{
135+
MaxDistance: curMaxDistance,
136+
Height: curHeight,
248137
}
249-
250138
}
251139
```
252140

0 commit comments

Comments
 (0)