LeetCode-Lowest Common Ancestor of a Binary Tree

这道题在一个面试的时候没有通过，当时没有想到两个要找的元素会连成一条线，所以，就gg了。

现在想来，这道题其实挺简单的，元素也只用遍历一次。

首先，要坚信输入的p和q是存在于root为根节点的二叉树中的。返回的时候就返回最有可能成为父节点的那个元素就可以了。首先，如果遍历到有元素等于p或者q，那么就说明根节点可能是他们（就是我没想到的那种情况），不管如何，直接返回，因为如果根节点不是它们，那么另一个要找的节点肯定在另外的递归中可以遇到，如果是他们，那就对了，先被返回的肯定是层级更高的，也就是另一个节点的父节点。

如果不是p或者q的话，那么就需要通过递归来找p和q是在该节点的左子树还是右子树中了，如果左右子树都能找到该节点，那么就说明这个节点就是要找的节点，直接返回就行了，注意在这里是递归搜索，所以一定是在搜索了它所有的子节点以后才去计算的结果。

最后，如果搜索的时候不是左右子树都有返回值的话，那就说明可能有一边有，也可能两边都没有，有一边有的话，这个问题就可以归约到第二行代码的问题中，直接把找到的那个节点返回就可以了，如果没找到的话，就返回空。

最后写下来，其实代码可以非常简洁，但是我面试的时候太蠢了，所以还是挂了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr) return nullptr;
        if(root==p || root==q) return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left!=nullptr && right!=nullptr) return root;
        if(left!=nullptr) return left;
        else return right;
    }
};