Use post order traverse the binary tree to solve with detailed explain,easy to understand way

• explain:
when we use a stack to traverse the binary tree, once meet the node , a path which is from root to this node displayed . Also ,we find the two nodes' path ,then, we reversely traverse the stack ,the first same node is the LCA

``````public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
List<TreeNode> first = new ArrayList<TreeNode>();
List<TreeNode> second = new ArrayList<TreeNode>();
getPath(root, p, first);
getPath(root, q, second);
return getCommonNode(first, second);
}

private TreeNode getCommonNode(List<TreeNode> first, List<TreeNode> second) {
for (int i = first.size()-1; i >=0 ; i--) {
TreeNode temp = first.get(i);
for(int j=second.size()-1; j>=0; j--){
if(temp == second.get(j)){
return temp;
}
}
}

return null;
}

private void getPath(TreeNode root, TreeNode node, List<TreeNode> path) {
TreeNode temp = root;

do{
while(temp != null){
if(node == temp){
return;
}
temp = temp.left;
}

TreeNode t = null;
boolean flag = true;

while(flag && path.size() > 0){
temp = path.get(path.size()-1);
if(temp.right == t){
t = path.remove(path.size()-1);
}else{
flag = false;
temp = temp.right;
}
}

}while(path.size() > 0);

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.