forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLCA.java
More file actions
132 lines (107 loc) · 3.16 KB
/
LCA.java
File metadata and controls
132 lines (107 loc) · 3.16 KB
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
package Algorithms.tree;
/**
* 1
* 2 3
* 4 5 6 7
* 9
*
*
* 1. find 1, 3
* 2. find 4, 7
* 3. find 4, 5
* 4, find 6, 9
* @author zhangyu
*
* * 3
* 2 6
* 1 5 7
* 9
*
*
* 1. find 1, 3
* 2. find 4, 7
* 3. find 4, 5
* 4, find 6, 9
* @author zhangyu
*
*/
public class LCA {
private static int cnt = 0;
public static void main(String[] strs) {
// TreeNode node1 = new TreeNode(1);
//
// TreeNode node2 = new TreeNode(2);
// TreeNode node3 = new TreeNode(3);
// TreeNode node4 = new TreeNode(4);
// TreeNode node5 = new TreeNode(5);
// TreeNode node6 = new TreeNode(6);
// TreeNode node7 = new TreeNode(7);
// TreeNode node9 = new TreeNode(9);
//
// node1.left = node2;
// node2.left = node4;
// node2.right = node5;
//
// node1.right = node3;
// node3.left = node6;
// node3.right = node7;
//
// node7.right = node9;
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node9 = new TreeNode(9);
node3.left = node2;
node3.right = node6;
node2.left = node1;
node6.left = node5;
node6.right = node7;
node7.right = node9;
LCA lca = new LCA();
//TreeNode rst = lca.getLCA(node1, node1, node3);
//TreeNode rst = lca.getLCA(node1, node4, node7);
//TreeNode rst = lca.getLCA(node1, node4, node5);
//TreeNode rst = lca.getLCA(node1, node6, node9);
TreeNode rst = lca.getLCABST(node3, node7, node9);
if (rst == null) {
System.out.print(0);
return;
}
System.out.println(rst.toString());
System.out.println(cnt);
}
public TreeNode getLCA(TreeNode root, TreeNode node1, TreeNode node2) {
cnt++;
if (root == null || node1 == root || root == node2) {
return root;
}
TreeNode left = getLCA(root.left, node1, node2);
TreeNode right = getLCA(root.right, node1, node2);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return null;
}
public TreeNode getLCABST(TreeNode root, TreeNode node1, TreeNode node2) {
cnt++;
if (root == null || node1 == root || root == node2) {
return root;
}
if (root.val > node1.val && root.val > node2.val) {
return getLCABST(root.left, node1, node2);
} else if (root.val < node1.val && root.val < node2.val) {
return getLCABST(root.right, node1, node2);
}
return root;
}
}