Repository navigation
Expand file tree
/
Copy pathLCABinaryTree.java
More file actions
103 lines (87 loc) · 2.49 KB
/
Copy pathLCABinaryTree.java
File metadata and controls
103 lines (87 loc) · 2.49 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
/**
* Created by Samarth on 3/13/2015.
*/
package LeetCode;
import java.util.*;
import LeetCode.LevelOrderTraversal.TreeNode;
public class LCABinaryTree {
public static void main(String args[]) throws Exception
{
TreeNode root = 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);
root.left = node2;
root.left.left = node3;
root.left.right = node4;
root.right = node5;
root.right.left = node6;
TreeNode lca = lowestCommonAncestor(root, node3, node4);
System.out.println(lca.val);
}
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode n1, TreeNode n2) {
List<TreeNode> pathN1 = new ArrayList<TreeNode>();
List<TreeNode> pathN2 = new ArrayList<TreeNode>();
findPath(root, n1, pathN1);
findPath(root, n2, pathN2);
/*for (int value : pathN1)
{
System.out.print(value + " ");
}
System.out.println();
for (int value : pathN2)
{
System.out.print(value + " ");
}*/
// Find the first element between the lists that is not common
int minPath = (pathN1.size() < pathN2.size()) ? pathN1.size() : pathN2.size();
int pos = 0;
for (int i=0; i<minPath; i++)
{
if (i == (minPath-1))
{
if (pathN1.get(i) == pathN2.get(i))
{
pos = i;
break;
}
}
if (pathN1.get(i) != pathN2.get(i))
{
pos = i-1;
break;
}
}
return pathN1.get(pos);
}
static boolean findPath(TreeNode root, TreeNode n1, List<TreeNode> pathN1)
{
if (root == null)
{
return false ;
}
pathN1.add(root);
//System.out.println("Inserting " + root.data);
if (root == n1)
{
return true;
}
else
{
if ((findPath(root.left, n1, pathN1) == false) && findPath(root.right, n1, pathN1) == false)
{
pathN1.remove(root);
return false;
}
}
return true;
}
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}