题解 | #在二叉树中找到两个节点的最近公共祖先#

1.递归

思路：

我们也可以讨论几种情况：

• step 1：如果o1和o2中的任一个和root匹配，那么root就是最近公共祖先。
• step 2：如果都不匹配，则分别递归左、右子树。
• step 3：如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最近公共祖先.
• step 4：如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。
• step 5：继续递归左、右子树，直到遇到step1或者step3的情况。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    // void find(TreeNode* root, int o1,stack<TreeNode*> &s)
    // {

    // }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        if(!root)
            return -1;
        //寻找o1、o2所在的结点
        if(root->val == o1 || root->val == o2)
            return root->val;//返回一个值以便与-1区分开来，以显示存在该结点
        //去左子树寻找o1、o2
        int left = lowestCommonAncestor(root->left, o1, o2);
        //去右子树寻找o1、o2
        int right = lowestCommonAncestor(root->right, o1, o2); 
        //如果左子树o1、o2都没有，则公共祖先在右子树中 
        if(left == -1)
            return right;
        //如果右子树o1、o2都没有，则公共祖先在左子树中
        if(right == -1)
            return left;
        //如果左右子树都找到了o1或o2，说明两个结点一个在左子树，一个在右子树，因此当前结点必是最近公共祖先
        return root->val; 
    }
};

2.路径比较法

思路：

既然要找到二叉树中两个节点的最近公共祖先，那我们可以考虑先找到两个节点全部祖先，可以得到从根节点到目标节点的路径，然后依次比较路径得出谁是最近的祖先。

找到两个节点的所在可以深度优先搜索遍历二叉树所有节点进行查找。

具体做法：

• step 1：利用dfs求得根节点到两个目标节点的路径：每次选择二叉树的一棵子树往下找，同时路径数组增加这个遍历的节点值。
• step 2：一旦遍历到了叶子节点也没有，则回溯到父节点，寻找其他路径，回溯时要去掉数组中刚刚加入的元素。
• step 3：然后遍历两条路径数组，依次比较元素值。
• step 4：找到两条路径第一个不相同的节点即是最近公共祖先。

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    //记录是否找到到o的路径
    bool flag = false;
    //求得根节点到目标节点的路径
    void dfs(TreeNode* root, vector<int> &path,int o)
    {
        if(flag || !root)
            return;
        path.push_back(root->val);
        //节点值都不同，可以直接用值比较
        if(root->val == o)
        {
            flag = true;
            return;
        }
        //dfs遍历查找
        dfs(root->left,path,o);
        dfs(root->right,path,o);
        //如果找到，返回
        if(flag)
            return;
        //如果该子树没有，回溯
        path.pop_back();
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        //求根节点到两个节点的路径
        vector<int> path1,path2;
        dfs(root,path1,o1);
        flag = false;//重置flag，查找下一个
        dfs(root,path2,o2);
        int res = -1;
        //比较两个路径，找到第一个不同的点
        for(int i = 0;i<path1.size() && i <path2.size();i++)
        {
            if(path1[i] == path2[i])
                res = path1[i];//最后一个相同的节点就是最近公共祖先
            else
                break;
        }
        return res;
    }
};