题解 | #农场牛群族谱#

考察知识点： 深度优先搜索、树的遍历

题目分析：

 首先画图考虑可能出现的结果：

 第一种是两个节点一个在某个子树的左子树中，一个在右子树中：

 第二种是两个节点都在某个子树的左子树中或右子树中：

 首先我们应该遍历一下树，在找到p或q时返回该节点的指针。在上述例子中，如果我们从节点2开始深度优先遍历树，一旦找到节点就立刻返回该指针，则可能会产生三种情况：

1. 遍历左子树时返回了非空指针，遍历右子树时也返回了非空指针。这说明当前的节点就是我们要找的节点。因为如果再比2高一层的话，p和q一定在那棵子树的同一侧，例如下图中4和10都在节点1的左子树中：

2. 遍历左子树时返回了非空指针，遍历右子树时返回了空指针。此时说明最少有一个节点在左子树上。若左子树中只满足一个节点，则返回该左子树的根节点向前归并时，当遇到上层节点有遍历右子树返回非空指针时，我们想要的结果就是此时的根节点；若左子树中有两个满足条件的节点，那么这个非空指针是结果，向上传递即可。

3. 当左子树和右子树都返回空指针时，说明该节点下方没有满足条件的子树，直接返回nullptr。

所用编程语言： 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整型
     */

    TreeNode* traversal (TreeNode *root, int p, int q) {
        if (!root || root->val == p || root->val == q) return root;
        TreeNode *left = traversal(root->left, p, q);
        TreeNode *right = traversal(root->right, p, q);
        if (!left) return right;
        if (!right) return left;
        return root;
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if (!root) return -1;
        TreeNode *res = traversal(root, p, q);
        return res->val;
    }
};