-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlowestCommonAncestor.java
More file actions
50 lines (46 loc) · 1.24 KB
/
Copy pathlowestCommonAncestor.java
File metadata and controls
50 lines (46 loc) · 1.24 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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// time: o(n)
// space: o(n)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int parentVal = root.val;
int pVal = p.val;
int qVal = q.val;
if(pVal > parentVal && qVal > parentVal){
return lowestCommonAncestor(root.right, p, q);//因为是bst所以值都大于root都在右边
}
else if(pVal < parentVal && qVal < parentVal){
return lowestCommonAncestor(root.left, p, q);//值都小于root在左边
}
else{
return root; //如果都没有就是root
}
}
}
//time o(n )
//space o(1)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int pVal = p.val;
int qVal = q.val;
TreeNode node = root;
while(root != null){
if(p.val > node.val && q.val > node.val){
node = node.right;
}
else if(p.val < node.val && q.val < node.val){
node = node.left;
}
else{
return node;
}
}
return null;
}