【LetMeFly】236.二叉树的最近公共祖先：深度优先搜索（巧用位运算）
力扣题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
- 树中节点数目在范围
[2, 105] 内。
-109 <= Node.val <= 109- 所有
Node.val 互不相同 。
p != qp 和 q 均存在于给定的二叉树中。
方法一：深搜确定路径，然后匹配
定义一个函数进行深搜，如果搜索到待寻找元素就返回当前节点到寻找节点的路径，否则就返回“空”
1
2
3
4
5
6
7
8
9
| vector<TreeNode*> dfs(TreeNode* root, TreeNode* finding) {
如果当前节点为空，就返回空数组
如果当前节点就是待搜索元素，就返回{当前元素}
对左子树进行搜索，如果左子树中找到了代寻找节点（不空），就返回“左子到待寻找元素的路径 + 这个点”
右子树同理
左右子树都找不到，就返回空数组
}
|
这样，我们就可以确定根节点到第一个待寻找节点的路径，也可以确定根节点到第二个待寻找节点的路径。
将第一个路径用哈希表存起来，第二个路径从待寻找元素往根节点遍历，第一个存在于哈希表中的元素就是两个节点的最近公共祖先。
- 时间复杂度$O(n)$，其中$n$是二叉树节点的个数
- 空间复杂度$O(n)$
AC代码
C++
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
| class Solution {
private:
vector<TreeNode*> dfs(TreeNode* root, TreeNode* finding) {
if (!root)
return {};
if (root == finding)
return {finding};
vector<TreeNode*> left = dfs(root->left, finding);
if (left.size()) {
left.push_back(root);
return left;
}
vector<TreeNode*> right = dfs(root->right, finding);
if (right.size()) {
right.push_back(root);
return right;
}
return {};
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pathP = dfs(root, p);
vector<TreeNode*> pathQ = dfs(root, q);
unordered_set<TreeNode*> se;
for (auto& thisNode : pathP) {
se.insert(thisNode);
}
for (auto& thisNode : pathQ) {
if (se.count(thisNode)) {
return thisNode;
}
}
return nullptr;
}
};
|
方法二：：深度优先搜索 + 巧用位运算
正常深搜（DFS），深搜过程中使用一个“状态”表示“当前节点及其子节点中PQ的存在情况”。
这样，第一个满足$状态=PQ都存在$的节点就是要找的答案（最近公共祖先）。
怎么表示“状态”呢？
可以使用二进制（位运算），用一个二进制位表示子树中是否有节点p和节点q，例如：
- 0($00_2$)表示PQ都不存在
- 1($01_2$)表示P存在Q不存在
- 2($10_2$)表示P不存在Q存在
- 3($11_2$)表示PQ都存在
这样，$当前节点状态 | 左子树状态 | 右子树状态$即为$当前子树状态$（其中$|$为或运算）
AC代码
C++
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
| typedef int Status;
#define NONE 0
#define ONLYP 1
#define ONLYQ 2
#define BOTH 3
class Solution {
private:
TreeNode* ans;
Status dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) {
return NONE;
}
Status thisStatus = NONE;
if (root == p) {
thisStatus |= ONLYP;
}
if (root == q) {
thisStatus |= ONLYQ;
}
thisStatus |= dfs(root->left, p, q) | dfs(root->right, p, q);
if (thisStatus == BOTH && !ans) {
ans = root;
}
return thisStatus;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
ans = nullptr;
dfs(root, p, q);
return ans;
}
};
|
Python
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
|
class Status:
none = 0
onlyP = 1
onlyQ = 2
both = 3
class Solution:
def dfs(self, root: Optional[TreeNode], p: 'TreeNode', q: 'TreeNode') -> Status:
if not root:
return Status.none
thisStatus = Status.none
if root == p:
thisStatus |= Status.onlyP
if root == q:
thisStatus |= Status.onlyQ
thisStatus |= self.dfs(root.left, p, q) | self.dfs(root.right, p, q)
if thisStatus == Status.both and not self.ans:
self.ans = root
return thisStatus
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
self.ans = None
self.dfs(root, p, q)
return self.ans
|
同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126782886