# post order iterative solution using just set and stack, better than hashMap version with explanation

• using post order iterative way can help us record the parent path along iteration without HashMap.

1. after find the first target node(p || q), put the current parent path from stack into set.
2. after find the second target node, the stack has its parent path, just double break to get out of the double while loop.
3. find the common ancester
``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<TreeNode> stack = new Stack();
if(root == null) return null;

TreeNode cur = root, prev = null;
boolean foundOne = false;
Set<TreeNode> set = new HashSet(); //for first found node's parent path
while(!stack.isEmpty() || cur != null)
{
while(cur != null)
{
stack.push(cur);
if((cur == p || cur == q) && !foundOne) //found first node
{
foundOne = true;
}
else if(cur == p || cur == q) break; //found second node, exit while loop
cur = cur.left;
}
if((cur == p || cur == q) && foundOne) break; //found second node, exit while loop

cur = stack.peek();
if(cur.right != null && prev != cur.right)
{
cur = cur.right;
}
else
{
prev = stack.pop();
cur = null;
}
}

//if p is q's lca, p's path must be stored in the set first.
while(!stack.isEmpty())
{
cur = stack.pop();
if(set.contains(cur)) return cur;
}
return null;
}
}
``````

}

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