I think of Stack at first glance, and then write this solution.

My idea is that this problem ask to find a Lowest Common Parent node. With Stack and post-order traversal, we can keep the parent node in the Stack.

Every time a node is visited (which means they will never get into the Stack), the code will check if it is a target node.

- For the first found node, we use one node lcp to remember the parent of it.
- If the current lcp is removed before we find the second target node, lcp will be replaced by its parent.

p.s. there are in fact only 2 situation

- Target node p is a parent/ancestor of node q
- They are separately in left subtree and right subtree.

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// Post-order traversal
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode lcp = null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root, pre = null;
int count = 0;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
if (cur.right == null || cur.right == pre) {
if (cur == p || cur == q) {
count++;
if (count == 1) lcp = stack.peek(); // !stack.isEmpty();
if (count == 2) return lcp;
}
if (cur == lcp) lcp = stack.peek(); // !stack.isEmpty();
pre = cur;
cur = null;
} else {
stack.push(cur);
cur = cur.right;
}
}
}
return lcp;
}
}
```