【leetCode】Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

大意：

在一个二叉树中查找两个结点的最近公共祖先节点。

思路：

判断一个一个结点root是否是两外两个结点A,B的公共祖先节点，是看A、B是否分别位于root结点的两侧子树中。且root的子节点均不能满足这一性质。

之前写的时候脑子进水，还专门写了函数去递归查找某个结点node是否在另一个结点的左/右子树中。越高越复杂，实现了功能却超时了。看了下别人的思路，简单明了得多。而且判断公共祖先节点的方法还跟我是一样的，果断学习之。

除了上面这个性质以外，另外一道题（给的不是常规二叉树而是一颗二叉搜索树）还可以根据二叉搜索树的性质去查找A/B两个结点，也很快。

one more thing，有个小细节~查找p和q这两个结点的时候，是用的root == q，意思是判断root和q是不是指向同一个对象。而非用的root->val == q->val去判断。别问我为什么会想到说这个，写完了测试不通过检查了N遍才发现。

class Solution
{
    public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        //root不存在就返回NULL
        if(!root)
            return NULL;
        //如果root是p或者q中的一个，就返回它
        if(root == p || root == q)
            return root;
        //如果root既不是p也不是q；
        //1.先从它左边找起
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        //2.然后再找找右边
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        //如果left和right都不为空，说明p和q都已经处于root两边了，root就是要找的LCA
        if(left && right)
            return root;
        //如果left和right有一个为空，说明p和q都位于非空的那一侧
        return left ? left : right;        
    }
};