Lowest Common Ancestor of a Binary Tree

题目

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

-w953

想法

自己想的是,dfs找到两者的路径,然后比较两者相同的前缀。

不过,看了discussion中的一个解答之后,发现自己还真是naive了,看准情况,暴力的才是最好的!

答案

我的答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* 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 {
private:
map<int, vector<TreeNode*>> path;
vector<TreeNode*> curr;
void dfs(TreeNode* node, int k) {
if (!node)
return;
curr.push_back(node);
if (node->val == k) {
path[k] = curr;
} else {
dfs(node->left, k);
dfs(node->right, k);
}
curr.pop_back();
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root, p->val);
dfs(root, q->val);
TreeNode* res = root;
int i = 0;
while (true) {
if (i >= path[p->val].size() || i >= path[q->val].size() || path[p->val][i] != path[q->val][i]) {
break;
} else {
res = path[p->val][i];
i++;
}
}
return res;
}
};

discussion中某位的答案:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/65225/4-lines-C++JavaPythonRuby

1
2
3
4
5
6
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
return !left ? right : !right ? left : root;
}