在数据结构中，二叉树是一个比较复杂的数据结构。在面试的时候，很多面试官喜欢通过二叉树来考察一个程序猿的逻辑、代码等基本功。最近正好在看《剑指offer》，并且学习了二叉树的一些相关知识。
在《剑指offer》的第50题，求二叉树中两个节点的最近公共祖先。关于这个题，其实刚看到题目的时候，容易顺着已有的思路忽略题目埋下的坑。首先我们要清楚这棵二叉树是怎样的一棵树，是搜索二叉树？还是只是平常的二叉树？如果是平常的二叉树，它有指向父节点的指针吗？……下来，我们一一分析每一种情况。
如果当前的树是一棵搜索二叉树，那么题目将会变得简单。搜索二叉树的节点分布是有规律的，如果我们要查找的节点一个在根节点的左边，一个在根节点的右边，那么毫无疑问根节点就是最近的公共祖先。如果不是，我们可以将这种思路递归下去，需要查找最大的节点都小于根节点，那么肯定在左边。右边同理。
理清思路，代码实现就简单了。
Node* FindSameParent(Node* k1, Node* k2) { K min = 0; K max = 0; if ((k1->_key) > (k2->_key)) { min = k2->_key; max = k1->_key; } else { min = k1->_key; max = k2->_key; } Node* cur = _root; while (cur) { if (max >= cur->_key && min <= cur->_key) return cur; if (max < cur->_key) cur = cur->_left; if (min>cur->_key) cur = cur->_right; } return NULL; }如果是一棵普通的树，我们需要考虑其特殊情况，如果它有指向父节点的指针，那么这个题就可以转换成我们之前学习的链表。如果没有父节点，我们就需要对整个树进行遍历去找这个节点。
a.有父节点
如果当前这棵树是有父节点，那么我们就可以顺着根节点一直遍历到我们需要查找的节点， 把这个路径保存到链表中，就变成了寻找两个链表的公共节点。
b.无父结点
如果没有父节点，那我们就只能对这个树进行遍历，遍历到一个节点的时候，判断这两个节点其中一个是否存在，如果存在就立即返回。主要是采用递归的思路一次判断。如果一个节点即有第一个需要查找的节点，也有第二个，那么它就是我们所求的节点。因为是递归，所以查找到的节点就是最近的。
这个思路并不难，下来看代码实现。
Node* _FindSameParent(Node* root, Node* k1, Node* k2) { if (root == NULL) return NULL; if (root == k1 || root == k2) return root; Node* _k1 = _FindSameParent(root->_left, k1, k2); Node* _k2 = _FindSameParent(root->_right, k1, k2); if (_k1 && _k2) return root; return _k1 ? _k1 : _k2; }以上的思路是我参考《剑指offer》一步一步进行分析的，其实如果这个一个普通的树，我们用上面的思路去分析，再用代码实现是比较复杂的。比如第一个转换成求链表的公共节点，我们都知道链表增删查改的时间复杂度为O(n)；第二个用递归，如果这棵树的比较大，堆栈的开销又太大，而且递归的次数较多，时间也比较慢。
在我用链表解决第一种情况时，查看STL的函数时。看到栈的时候，发现这两种情况都可以用栈解决，并且栈的查找时间复杂度为O(1)。这样对整个查找的情况即简单化，而且效率也高。
我们现在用两个栈去保存我们遍历过的路径，然后保证两个栈的大小是一样的，然后进行出栈操作，这样也可以找到最近的公共节点。
这里就需要一个函数来得到路径，在查找路径一定要明白：如果在左子树查找成功，那么一定不存在在右子树（这里我们不考虑树中有相同的节点）。如果查找的路径不对，一定要记得最后把该节点pop出，否则栈里的元素就存在问题了。
bool _GetPath(Node* root, Node* k, stack<Node*>& s) { if (root == NULL) return false; if (k == root) { s.push(root); return true; } s.push(root); if(_GetPath(root->_left, k, s)) return true; if(_GetPath(root->_right, k, s)) return true; s.pop(); return false; }查找的代码实现如下。
Node* FindSameParent(Node* k1, Node* k2) { if (_root == NULL) return NULL; stack<Node*> s1; stack<Node*> s2; _GetPath(_root, k1, s1); _GetPath(_root, k2, s2); while (s1.size() > s2.size()) { s1.pop(); } while (s1.size() < s2.size()) { s2.pop(); } while (s1.top() != s2.top()) { s1.pop(); s2.pop(); } return s1.top(); }写完这道题再来看题目，这道题本身并不难，难得是我们如何考虑到出现的情况，如何把未知的问题转变成我们学过的知识。在写代码前，一定要先分析可能出现的情况，要跳出自己的惯性思维方式，客观去理解看待问题。
