LeetCode刷题实战236:二叉树的最近公共祖先
程序IT圈
共 5356字,需浏览 11分钟
·
2021-04-14 14:03
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
示例
解题
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode *> stack;
stack.push(root);
map<TreeNode *, TreeNode *> parent_map;
parent_map[root] = NULL;
while(parent_map.find(p) == parent_map.end() || parent_map.find(q) == parent_map.end()){
TreeNode *node = stack.top();
stack.pop();
if(node -> left != NULL){
parent_map[node -> left] = node;
stack.push(node -> left);
}
if(node -> right != NULL){
parent_map[node -> right] = node;
stack.push(node -> right);
}
}
set<TreeNode *> p_parent;
p_parent.insert(p);
// 迭代父节点map,这里的循环逻辑为,父节点字典中如果一直能够找到p节点的父节点,就进入循环
// 这样可以一直得到p节点的父节点列表。
while(parent_map.find(p) != parent_map.end()){
p_parent.insert(parent_map[p]);
p = parent_map[p];
}
// 同理遍历q节点的父节点列表,因为是逆序遍历,所以当它存在于p节点的列表时,找到的就是p和q的最近公共祖先
while(parent_map.find(q) != parent_map.end()){
if(p_parent.find(q) != p_parent.end()){
return q;
}
q = parent_map[q];
}
return root;
}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
int num = contain_node(root, p, q);
return ans;
}
int contain_node(TreeNode* root, TreeNode* p, TreeNode* q){
if(!root) return 0;
int mid = 0;
if(root == p || root == q) mid = 1;
int left = contain_node(root -> left, p, q);
if(mid + left == 2){
if(!ans) ans = root;
return 2;
}
int right = contain_node(root -> right, p, q);
if(left + right + mid >= 2){
if(!ans) ans = root;
return 2;
}
return left + mid + right;
}
private:
TreeNode* ans = NULL;
};
评论