传送门：236. 二叉树的最近公共祖先
题目给我们一棵树以及树上的两个节点。要我们求两个节点的最近公共祖先。什么叫祖先呢，只要是与这个节点的有血缘关系的父节点，包括其自身都可以称作这个节点的祖先。而要我们求节点的最近公共祖先，不由得让人想到用找两个树时的路径进行对比。若分别找到二者的路径，则这个问题便演变成了找两个链表交点的问题。
现在的主要问题就是该如何找节点的路径？不妨使用DFS算法进行实现，用栈进行存储。由于DFS会不断深入和回溯，每次走错路就将之前的路径出栈，否则便继续深入，直到找到目标节点为止。最后用两个栈进行查找第一个相同的节点便可以解决问题。
bool getpath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path) { if(root == nullptr) return false; //走到空节点即找不到返回失败 path.push(root); //走到新节点就先入栈 if(root == x) return true; //找到目标节点返回成功 if(getpath(root->left,x,path)) //判断往左找是否成功 { return true; } if(getpath(root->right,x,path)) //判断往右找是否成功 { return true; } path.pop(); //出栈 return false; //都没有就返回失败 } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*> ppath,qpath; //定义两个栈用于存储路径 getpath(root,p,ppath); //求p的路径 getpath(root,q,qpath); //求q的路径 while(ppath.size()!= qpath.size()) { if(ppath.size()>qpath.size()) //把长的部分去掉使得两个栈一样长 { ppath.pop(); } else { qpath.pop(); } } while(ppath.top()!=qpath.top()) //找第一个相同节点 { ppath.pop(); qpath.pop(); } return ppath.top(); }
