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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    TreeNode* dfs(TreeNode* root,int o1,int o2){
        //空节点，返回自己
        if(!root) return root;
        //若是指定节点，返回自己
        if(root -> val == o1 || root -> val == o2) return root;
        //当root既不是空节点,又不是指定节点时，就去找它的左右子树中是否有指定节点
        TreeNode* l = dfs(root -> left,o1,o2);
        TreeNode* r = dfs(root -> right,o1,o2);
        //若它的左右子树都没有指定节点，那么他肯定也不是最近公共祖先了，返回空
        if(!l && !r) return nullptr;
        //若右子树有指定节点的话，就返回右子树传上来的节点(这个节点可能为公共祖先，也有可能仅为指定节点)
        if(!l) return r;
        //若左子树有指定节点的话，就返回左子树传上来的节点（同上）
        if(!r) return l;
        //若左右子树都有，根据二叉树的特性，这样的节点唯一，且为这两个节点的最近公共祖先，就向上传自己root
        return root;
    }


    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        //若其中一个节点为根节点，直接返回根节点
        if(root -> val == o1 || root -> val == o2){
            return root -> val;
        }
        return dfs(root,o1,o2) -> val;
    }
};

这道题目首先要想明白一个问题，两个指定节点一定分别分布于他们公共祖先的左右子树中：

假设有一个节点root

• root的左子树和右子树都不存在指定节点，那么root一定不是最近公共祖先。
• root的左子树存在指定节点，而右子树不存在指定节点，那么root要么为左子树找到的那个指定节点的祖先，或者为最近公共祖先的祖先(这取决于另一个指定节点是否在root的左子树中，但这两种情况与本题无关，反正root在这种情况下就不是最近的公共祖先)
• 与上面相反，左右互换即可
• root的左右子树都存在指定节点，那么root就一定是最近的公共祖先。

那么如何去root的左右子树中找指定节点呢，当然就用dfs了。

只是在常规遍历的基础上，加了几个条件：

1. 把指定节点也当作递归结束的条件（与空节点一样），如果找到了指定节点，就不用继续递归找下面的节点了，返回自己即可。

（这里可能会存在疑惑，若第二个指定节点是当前指定节点的孩子，那么第二个指定节点不就是没有访问到吗？

确实，但是本题是求最近公共节点，若第二个指定节点都是第一个指定节点的孩子了，那最近的公共祖先节点就是第一个 指定节点了。）

2.

当前root在遍历完左右子树后，会知道左右子树是否有指定节点，由此来判断root是不是最近的公共祖先，具体见上文，只有 作为最近公共祖先时才返回自己，否则返回左右子树传上来的节点。

形象点说就是：当前root通过自己左右子树的情况得知了自己的身份，于是就告诉自己的领导：

a. 领导，我是你的左(右)孩子,我不是指定节点的最近公共祖先，并且我的左右子树都没有指定节点，不要管我了，我把NULL传给你。
b. 领导，我是你的左(右)孩子,我不是指定节点的最近公共祖先，我左(右)子树有指定节点，我把我的左(右)下级的传过来的信息给你。
c. 领导，我是你的左(右)孩子,我是指定节点的最近公共祖先，我把自己传给你。

最后消息传到最大的领导的手上之后，领导在根据自己的两个左右下级判断一下，得出最大公共祖先。

以上是我的思考与总结，讲得不对的地方希望大家多多指正。