二叉树的最近公共祖先—leetcode236

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

方法1：第一遍只能想到这个笨办法了，按行遍历，把包含两个节点的节点保存下来，取最后一个公共节点。

/**
 * 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:
    queue<TreeNode*> commonNodes;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        queue<TreeNode*> nodes;
        if(root==NULL)
            return NULL;
        nodes.push(root);
        while(!nodes.empty()){
            TreeNode* front = nodes.front();
            nodes.pop();

            if(isexist_p(front,p)&&isexist_q(front,q))
                commonNodes.push(front);

            if(front->left) nodes.push(front->left);
            if(front->right) nodes.push(front->right);
        }
        return commonNodes.back();
    }

    bool isexist_p(TreeNode* root, TreeNode* p){
        if(root==p){
            return true;
        }
        if(root==NULL){
            return false;
        }
        return isexist_p(root->right,p) || isexist_p(root->left,p);
    }

    bool isexist_q(TreeNode* root, TreeNode* q){
        if(root==q){
            return true;
        }
        if(root==NULL){
            return false;
        }
        return isexist_q(root->right,q) || isexist_q(root->left,q);
    }
};

解法二：

做了一些二叉树的题，发现二叉树的查找问题一般都是从左右子树递归去解决，也往往都能得到答案，因此，这道题可以考虑是否能从左右子树进行递归去解决呢？
首先，要想通过递归来实现，就需要先确定临界条件，那么临界条件是什么呢？换句话说，临界条件就是递归中能够直接返回的特殊情况，第一点则是最常见的“判空”，判断根结点是否是空节点，如果是，那么肯定就可以马上返回了，这是一个临界条件；再来考虑题意，在以root为根结点的树中找到p结点和q结点的最近公共祖先，那么特殊情况是什么呢？很显然，特殊情况就是根结点就等于q结点或p结点的情况，想一下，如果根结点为二者之一，那么根结点就必定是最近公共祖先了，这时直接返回root即可。由此看来，这道题就一共有三种特殊情况，root == q 、root == p和root==null，这三种情况均直接返回root即可。
根据临界条件，实际上可以发现这道题已经被简化为查找以root为根结点的树上是否有p结点或者q结点，如果有就返回p结点或q结点，否则返回null。
这样一来其实就很简单了，从左右子树分别进行递归，即查找左右子树上是否有p结点或者q结点，就一共有4种情况：
第一种情况：左子树和右子树均找没有p结点或者q结点；（这里特别需要注意，虽然题目上说了p结点和q结点必定都存在，但是递归的时候必须把所有情况都考虑进去，因为题目给的条件是针对于整棵树，而递归会到局部，不一定都满足整体条件）
第二种情况：左子树上能找到，但是右子树上找不到，此时就应当直接返回左子树的查找结果；
第三种情况：右子树上能找到，但是左子树上找不到，此时就应当直接返回右子树的查找结果；
第四种情况：左右子树上均能找到，说明此时的p结点和q结点分居root结点两侧，此时就应当直接返回root结点了。

/**
 * 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==p||root==q)
            return root;

        if (root==NULL)
            return NULL;

        TreeNode* lNode=lowestCommonAncestor(root->left,p,q);
        TreeNode* rNode=lowestCommonAncestor(root->right,p,q);
        if(lNode!=NULL&&rNode!=NULL)
            return root;
        else if(lNode==NULL)//两个都在右子树
            return rNode;
        else//两个都在左子树里面
            return lNode;

        return NULL;
    }
};