题解 | #在二叉树中找到两个节点的最近公共祖先#

基本思路是通过递归来获取从根结点到目标结点的路径，两个结点的最近公共祖先就是其从根结点开始的路径上最后一个相同的结点。
具体实现是用两个栈来记录路径，从根结点开始向下递归，每次都将路径上的结点压栈。最后得到两个保存有路径的栈，对两个栈的栈顶进行比较，相同则记录该结点，并同时进行出栈操作，不同则返回上一次记录的结点。
在实现时有个问题，这个问题在之前做题的过程中也有遇到(二维数组层序遍历中的vector)，就是当一个数据结构，如栈、数组、队列等作为参数传入递归函数，并需要在递归函数中对该数据结构进行修改时，得到的结果往往是不正确的，所以需要将其在参数重去除，作为全部变量直接在函数中修改。其结果就如下面代码所示，不得不定义两个getPath函数，十分影响代码结构。具体原因还未查明，望知道的大佬告知。猜测可能是C++编译时的问题，因为java中不存在该问题。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    stack<int> s1;
    stack<int> s2;
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        getPath1(root, o1);
        getPath2(root, o2);
        int same = 0;
        while(s1.size() && s2.size()){
            if(s1.top() != s2.top()){
                return same;
            }
            same = s1.top();
            s1.pop();
            s2.pop();
        }
        return same;
    }
    bool getPath1(TreeNode* root, int p){
        if(root == NULL ){
            return false;
        }
        if(root->val == p || getPath1(root->left,p) || getPath1(root->right, p)){
            s1.push(root->val);
            return true;
        }
        return false;
    }
    bool getPath2(TreeNode* root, int p){
        if(root == NULL ){
            return false;
        }
        if(root->val == p || getPath2(root->left,p) || getPath2(root->right, p)){
            s2.push(root->val);
            return true;
        }
        return false;
    }
};

回头看了一下上面递归中stack操作出错的问题，发现是定义函数时入参的问题。修正后的代码如下，美观了很多。这一个问题涉及到传值和传引用的基础知识，将在另一篇笔记中做记录。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        stack<int> s1;
        stack<int> s2;
        getPath(root, o1,s1);
        getPath(root, o2,s2);
        int same = 0;
        while(s1.size() && s2.size()){
            if(s1.top() != s2.top()){
                return same;
            }
            same = s1.top();
            s1.pop();
            s2.pop();
        }
        return same;
    }
    bool getPath(TreeNode* root, int p,stack<int>& stk){
        if(root == NULL ){
            return false;
        }
        if(root->val == p || getPath(root->left,p,stk) || getPath(root->right, p,stk)){
            stk.push(root->val);
            return true;
        }
        return false;
    }

};