二叉树的一个经典问题是找到两个节点的最近公共祖先。
一个经典解法是找到从根节点到该节点的路径，然后两条路径找公共节点。
private boolean search(TreeNode root, TreeNode target, Deque<TreeNode> deque) {
if (root == null) {
return false;
}
deque.add(root);
if (root == target) {
return true;
}
boolean ret = search(root.left, target, deque);
if (ret) {
return ret;
}
ret = search(root.right, target, deque);
if (!ret) {
deque.removeLast();
}
return ret;
}
这段找路径的代码使用的算法是先序遍历，需要注意：
- 空树、单节点、两节点、三节点的单元测试
- 需要及时退出程序，注意此时deque的入队和出队。
后续代码：
TreeNode result = null;
while (!deque1.isEmpty() && !deque2.isEmpty()) {
TreeNode treeNode1 = deque1.removeFirst();
TreeNode treeNode2 = deque2.removeFirst();
if (treeNode1 == treeNode2) {
result = treeNode1;
} else {
break;
}
}
System.out.println(result);
