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

/**
 * 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 == nullptr) return nullptr;
       //公共祖先一定是自己或者自己上层的节点
        if(root -> val == o1 || root -> val == o2) return root;
        TreeNode* l = dfs(root -> left,o1,o2);
        TreeNode* r = dfs(root -> right,o1,o2);
        //如果左右返回都为null，证明这个节点的左右子树都没查到，返回null给上面通知
        if(!l && !r) return nullptr;
        //如果左边没找到，右边找到了的话，返回右边找到的结果。
        else if(!l) return r;
        else if(!r) return l;
        //如果左右子树都找到的话，那他就是最近公共祖先
        return root;
    }


    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        return dfs(root,o1,o2) -> val;
    }
};

dfs。由于是二叉树，所以若一个节点的左右子树分别查到两个节点时，他就是最近的公共祖先。若只有一个子树查到，证明它这个子树的中存在公共祖先。若两个子树都查不到，那告诉父节点自己的子树查不到。