Leetcode-236. 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.

二叉树的经典问题，也是笔试面试常考问题。

两种思路：第一种比较好想，就是找到两个节点p,q对应的root->....->p和root->....->q的路径，然后比较两个路径，找到最后一公共节点即可。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q) return root;
        vector<TreeNode*> s,t;
        findPath(root, p, s);
        findPath(root, q, t);
        int k = min(s.size(), t.size()), i = 1;
        for(;i<k;++i){
            if(s[i] != t[i]) break;
        } 
        return s[i-1];
    }
    bool findPath(TreeNode* root, TreeNode* node, vector<TreeNode*>& path){
        if (root == NULL)
            return false;
        path.push_back(root);
        if (root == node)
            return true;
        if (root->left && findPath(root->left, node, path) || 
            root->right && findPath(root->right, node, path))
            return true;
        path.pop_back();
        return false;
    }
};

第二种思路：递归寻找。如果p，q节点有一个是当前root节点，那就直接返回root节点，如果不是，就在左右子树中寻找p，q。如果在一个子树中找到p，另个子树找到q，那么当前root就是最小的公共祖先。如果都在同一个子树上，那就递归在这个子树中寻找p,q的公共祖先。代码非常简单。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        return !left ? right : !right ? left : root;
    }
};

后：不知道p,q中如果有一个点不在树中，这种情况有没有考虑过。好像方法二没对这种情况进行讨论。方法一的话对应bool的函数进行一个判断即可。另外方法一的话可以解决二叉树中两个节点之间最短路径这类问题。