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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    TreeNode* res = nullptr;
    bool dfs(TreeNode* root, int o1, int o2){     // 该子树是否存在o1或o2
        if(!root)
            return false;
        
        bool ifLeft_ok = dfs(root->left, o1, o2);
        bool ifRight_ok = dfs(root->right, o1, o2);
        bool ifCurr_ok = root->val==o1 || root->val==o2;

        if((ifLeft_ok && ifRight_ok) || (ifLeft_ok && ifCurr_ok) || (ifRight_ok && ifCurr_ok))
            res = root;
        return ifLeft_ok || ifRight_ok || ifCurr_ok;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        bool trash = dfs(root, o1, o2);
        return res->val;
    }
};

思路：

解题关键：如果“左子树找到了其中一个”、“右子树找到了其中一个”、“本节点就是其中一个”这三个条件任意满足两个，则当前节点即为所求。

TreeNode *res = nullptr;
bool dfs(root){		// 当前节点及一下的节点，是否存在o1、o2的其中一个
  if(空节点)
	return false;
  
  左边是否含有=dfs(左子树);
  右边是否含有=dfs(右子树);
  本节点是否含有=(root->val==o1 or root->val==o2);
  
  if(以上三点任意满足其二)
	res = root;
  return (以上三点任意满足其一);
}