这是《剑指Offer——名企面试官精讲典型编程题》一书中的面试题50，此题针对所给条件的不同，将需要截然不同的解题思路和方法。书中给出了针对此题的3种不同条件的解题，本文所要讲解的是对其第3种条件的一个改进解法。具体的题目及条件如下。
【题目】：
输入两个树结点，求它们的最低公共祖先。
【补充条件】：
树是普通的树，而且树中的结点没有指向父节点的指针。
针对上述的题目和条件，书中给出了如下解决方案。
【原方案】：
使用两个链表，对树进行两次遍历以查找两个树结点，并保持路径到两个链表中，从而将问题转化为求两个链表的最后一个公共结点。
从该方案中，观察到两次树结点查找的遍历中，其中一个结点的遍历过的树结点序列将完全覆盖查找另一结点时所遍历的树结点序列。由此入手，本文提出了如下的改进解决方案。
【改进方案】：
深度优先遍历树，并记录路径，当找到第一个结点后，在当前基础上继续遍历搜索第二个结点，并记录第一个结点路径的变化程度，直到找到第二个结点。最后，根据栈信息和记录的结点路径变化程度得到最低公共祖先。如图1，假设输入的两个树结点为D和K，树的根节点为R，则求D和K的最低公共结点的过程如下表：
|
步骤 |
栈 |
第一个结点 |
第二个结点 |
路径变化程度 |
|
1 |
R |
— |
— |
— |
|
2 |
R，A |
— |
— |
— |
|
3 |
R，A，F |
— |
— |
— |
|
4 |
R，A，F，J |
— |
— |
— |
|
5 |
R，A，F，G |
— |
— |
— |
|
6 |
R，A，F，K |
K |
— |
0（或K） |
|
7 |
R，A，C |
K |
— |
1（或A） |
|
8 |
R，A，C，E |
K |
— |
2（或A） |
|
9 |
R，A，C，I |
K |
— |
2（或A） |
|
10 |
R，A，D |
K |
D |
1（或A） |
|
è 得出结果，最低公共祖先结点为A |
从中，可以看到，改进后的方案，只需对树执行一次遍历。而在辅助空间的需求上， 只需使用一个栈（外加少量结点指针变量和1个表示路径变化程度的整型变量）。而且，如果采用递归的方式实现，该栈所需保存的信息，还可以通过递归时的函数调用栈得以保存。
【附注】：
- 此处，有如下一个问题：
假设待查找公共祖先的两树结点，其中一结点在以另一结点为根的子树上（包括两结点相同）时，公共祖先的确定规则——
“作为子树根结点的那个结点”还是“子树根结点的父节点”？
例如：对上面图1中的那棵树，如果待查结点为根结点R和结点F，那么最终的查找结果是为R呢，还是因为R是根结点无父结点而得出NULL？
此问题在书中未提及，但查看书中代码，确认是选择了后者；而在本人的样例代码中则采用了前面的观点。 - 在样例代码中，对树结点在栈中的存储方式略有改动。
- 样例代码工程所使用的环境为 Visual C++ 2010；
其中：tree.h/cpp为功能代码文件，TestLowestCommonAncestor.h/cpp为相应的UT代码文件；
UT采用gtest所编写，编译链接请根据gtest在自己本机的路径状况修改gtest_link.props文件中相应的链接项。