# Leetcode 236：二叉树的最近公共祖先

* p和q在相同子树中
* p和q在不同子树中

## 代码实现

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr || root == p || root == q) { return root; } TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left && right) { return root; } return left ? left : right;}

# Leetcode 238：除自身以外数组的乘积

## 代码实现1

vector<int> productExceptSelf(vector<int>& nums) { //先左再右 vector<int>resleft(nums.size(), 1); for (int i = 1; i < nums.size(); i++) { resleft[i] = resleft[i - 1] * nums[i - 1]; //cout << resleft[i] << " "; } //cout << endl; vector<int>resright(nums.size(), 1); for (int i = nums.size() - 2; i >= 0; i--) { resright[i] = resright[i + 1] * nums[i + 1]; //cout << resright[i] << " "; } //cout << endl; vector<int>result(nums.size(), 1); for (int i = 0; i < nums.size(); i++) { result[i] = resleft[i] * resright[i]; } return result;}

## 复杂度1

leetcode238resultzjz.jpg

## 代码实现2

vector<int> productExceptSelf(vector<int>& nums) { //先左再右 vector<int>result(nums.size(), 1); int k = 1; for (int i = 0; i < result.size(); i++) { result[i] = k; k *= nums[i]; } k = 1; for (int i = result.size() - 1; i >= 0; i--) { result[i] *= k; k *= nums[i]; } return result;}