Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
</pre>
Example 2:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
</pre>
Example 3:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input: root = [2,1], p = 2, q = 1
Output: 2
</pre>
Constraints:
- The number of nodes in the tree is in the range
[2, 10<sup>5</sup>]. -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>- All
Node.valare unique. p != q-
pandqwill exist in the BST.
我的答案：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> ancester1, ancester2;
SearchNode(root, p, ancester1);
SearchNode(root, q, ancester2);
// cout << ancester1[0]->val << " - " << ancester2[0]->val << endl;
int i = 1;
for (; i<ancester1.size() and i<ancester2.size(); ++i) {
// cout << ancester1[i]->val << " - " << ancester2[i]->val << endl;
if (ancester1[i] != ancester2[i]) {
return ancester1[i-1];
}
}
return ancester1[i-1]; // mark2
}
void SearchNode(TreeNode* root, TreeNode* node, vector<TreeNode*>& ancester) {
if (node->val == root->val) {
ancester.push_back(root); // mark1
return;
}
ancester.push_back(root);
if (node->val < root->val) {
SearchNode(root->left, node, ancester);
}
else {
SearchNode(root->right, node, ancester);
}
}
};
Runtime: 28 ms, faster than 90.94% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 24 MB, less than 24.08% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
感覺(jué)這么做下來(lái)，不是E的題潜腻。
- 首先需要想到是binary search tree衰猛，所以存儲(chǔ)每個(gè)node的ancestor比較容易了溃肪，正向搜索也只有唯一解
- 其次一個(gè)坑是mark1处嫌，需要把自己也放到ancestor里面
- 最后mark2的地方也需要注意糟描，到這一步說(shuō)明前面的ancestor匹配都對(duì)吨掌，只是size不同出來(lái)斩个，所以就需要return ancester1[i-1];胯杭，但注意不是return ancester1[i];，因?yàn)槌鰜?lái)的i已經(jīng)++過(guò)了
不過(guò)結(jié)合binary search tree的性質(zhì)萨驶，其實(shí)有更簡(jiǎn)單的方法
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/
官方答案
默寫(xiě)recursive答案：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* ans = root;
if (ans->val > p->val and ans->val > q->val) {
ans = lowestCommonAncestor(root->left, p, q);
}
else if (ans->val < p->val and ans->val < q->val) {
ans = lowestCommonAncestor(root->right, p, q);
}
// else {
// }
return ans;
}
};
Runtime: 36 ms, faster than 38.67% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.9 MB, less than 24.08% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
默寫(xiě)iterative答案：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* ans = root;
while (ans != p and ans != q) {
if (ans->val > p->val and ans->val > q->val) {
ans = ans->left;
}
else if (ans->val < p->val and ans->val < q->val) {
ans = ans->right;
}
else {
break;
}
}
return ans;
}
};
Runtime: 24 ms, faster than 98.52% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.9 MB, less than 24.08% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
