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

寻找目标节点到根节点的路径，用栈保存。从根节点开始出栈，只要两个栈的节点相同则出栈否则退出。最后一次出栈的就是最近的公共祖先。

/**
 * 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
        int rst = root->val;
        stack<TreeNode*> path_stack_o1;
        stack<TreeNode*> path_stack_o2;

        //查找出包含o1的路径;
        get_path(root,o1,path_stack_o1);
        //查找出包含o2的路径;
        get_path(root,o2,path_stack_o2);

        while(!path_stack_o1.empty() && !path_stack_o2.empty())
        {
            //相同的祖先;
            if(path_stack_o1.top() == path_stack_o2.top())
            {
                //更新结果;
                rst = path_stack_o1.top()->val;
                path_stack_o1.pop();
                path_stack_o2.pop();
            }else
            {
                //祖先不再相同，退出;
                break;
            }
        }

        return rst;
    }

    //查找路径;
    bool get_path(TreeNode* root, int target, stack<TreeNode*>& path_stack)
    {
        //从root节点查找存储的val为target的节点,返回值表示该路径存在该target;
        if(!root) return false;

        //如果该节点就是目标节点或者从该节点的左分支包含目标节点或者从该节点的右分支包含目标节点,返回true;
        //该节点不是目标节点则从左分支、右分支去判断是否存在目标节点;
        if(root->val == target)
        {
            path_stack.push(root);
            return true;
        }

        if(get_path(root->left,target,path_stack))
        {
            path_stack.push(root);
            return true;
        }

        if(get_path(root->right,target,path_stack))
        {
            path_stack.push(root);
            return true;
        }

        return false;
    }
};