题解 | #农场牛群族谱#

题目考察的知识点：二叉树的遍历

题目解答方法的文字分析：可以把要找的两个节点的路径找出来，然后存到栈里；我们先让节点入栈，然后判断它是否等于我们要找的节点，如果是，则返回true；如果不是，则1.如果左节点不为空，返回true；2.如果右节点不为空，返回true；3.如果左右节点都为空，则pop掉栈顶的元素，返回false；然后将栈的长度改为一样，最后寻找公共祖先。

本题解析所用的编程语言：c++

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */

    bool findpath(TreeNode* root,int& x, stack<int>& st)  //注意这里要传引用
    {
        if (root == nullptr)
            return false;
        st.push(root->val);
        if (findpath(root->left, x, st))
            return true;
        if (findpath(root->right, x, st))
            return true;
        if (root->val == x)
            return true;
        st.pop();
        return false;
    }

    int lowestCommonAncestor(TreeNode* root, int p, int q) 
    {
        // write code here
        stack<int> ppath, qpath;
        findpath(root, p, ppath);
        findpath(root, q, qpath);
        if (ppath.size() < qpath.size())
            swap(ppath, qpath);
        while (ppath.size() != qpath.size())
            ppath.pop();
        while (ppath.top() != qpath.top())
        {
            ppath.pop();
            qpath.pop();
        }
        return ppath.top();
    }
};