二叉树的最近公共祖先(Leetcode 剑指Offer68-Ⅱ)

1

题目分析

   有关树的题目,小伙伴们就要想到递归,这个要深深的印在脑海里面。本题和Leetcode 剑指Offer68-Ⅰ是姐妹类型,这个题目难度稍微大一些,上一题我没有拿出来讲解是因为过于简单。在二叉搜索树中查找,因为是搜索树,我们可以根据节点的大小选择固定的路,不用进行回溯,所以通过迭代即可,不用递归进行查找,**时间复杂度为$O(log(n))$。这个题目我们不知道树中节点的大小关系,因此需要进行递归查找,时间复杂度为$O(n)$**。

递归

在这里先给出我的笨方法,虽然时间复杂度和空间复杂度并不高,但是代码长度大,不美观。

我的思路是自底向上进行查找,当找到p或者q时,数量加1,当数量等于2时,说明该节点是最近的公共祖先。

算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。

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
43
44
45
#include<iostream>

using namespace std;

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) {
int nums = 0;
return subQuestion(root, p, q, nums);
}

TreeNode* subQuestion(TreeNode* root, TreeNode* p, TreeNode* q, int& nums) {
if (!root) {
return NULL;
}
int left = 0, right = 0;
TreeNode* leftChild = subQuestion(root->left, p, q, left);
TreeNode* rightChild = subQuestion(root->right, p, q, right);
nums = left + right;
if (root == p || root == q) {
nums++;
}
if (left == 2) {
return leftChild;
}
else if (right == 2) {
return rightChild;
}
else {
if (nums == 2) {
return root;
}
else {
return NULL;
}
}
}
};

优化递归

要找两个节点的最近公共祖先,现在有三种情况,一个是两个节点都在某个节点的左孩子中,第二个是两个节点都存在于某个节点的右孩子中,第三个是两个节点一左一右分别存在于左孩子和右孩子中。

我们自底向上进行查找,当找到p或者q时返回p和q,p和q一定在某个节点的左右子树上,一个在左,一个在右,如果没有找到该节点,那么左右子树一定有一个是NULL,如果left = NULL,则return right,如果right = NULL,则return left,如果左右都不是NULL,说明找到了最近的公共祖先,返回root即可。

这个思路是比较难想的,代码却非常简单,也非常漂亮。算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>

using namespace std;

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) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (!left) return right;
if (!right) return left;
return root;
}
};

刷题总结

  这个题目作为简单题,我不能接受,我想了很久,用了一种很笨的方法,虽然也是自底向上,但是代码不优美,这里提醒小伙伴们在刷题的时候,不能提交没有问题就进行下一题,一定要看一看别人的思路和方法,多多学习,这样才可以更好的提升自己。

-------------本文结束感谢您的阅读-------------
0%