235题——二叉搜索树的公共祖先
原题链接在这里——力扣235题
解题思路1
遇到这种题要首先想到递归法。
- 如果根节点为空，直接返回NULL；
- 如果left和right有一个为根节点，那么他俩的公共祖先必为根节点；
- 如果两个目标节点有一个为空，那么就返回另一个节点；
- 如果目标节点分居左右子树，那么必返回root；
- 如果上述情况均不满足(不可能)，就返回NULL。
代码如下
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(!root) return NULL;
TreeNode* left = lowestCommonAncestor(root->left, p, q);//注意这里的TreeNode*可以写成auto
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(root == p || root == q) return root;
if(left == NULL) return right;
if(right == NULL) return left;
if(left && right) return root;
return NULL;
}
解题思路2
采用栈的思想解决问题。问题的解决一共有两步：
- 首先从根节点开始遍历，到目标节点为止，记录途径节点，将其存放在栈内；
- 遍历到目标节点时，将两个栈从根节点开始比较。最后一个完全相同地址所对应的节点即为所求。
代码如下：
解题思路3
思路详解
使用哈希表记录每个节点的父节点。当找到目标节点p时，利用哈希表找到p的父节点并一一标记，不断向上寻找直到找到根节点；找到目标节点q时，仍然利用哈希表找到q的父节点，并查看是否已被标记。若没有标记则继续向上遍历，反之则返回该节点。 思路及步骤如下：
- 从根节点开始遍历二叉树，用哈希表记录每个节点和其父节点
- 从p开始不断找到它的父节点并标为已访问，直到根节点
- 从q开始找到它的父节点（包括q）查看是否已被标记，被标记则返回 算法复杂度： 由于遍历所有节点，因此时间复杂度为O(N)； 由于新建的哈希表map大小为n，因此空间复杂度为O(N)：
代码如下：
//哈希表put和get在c++里面对应着什么呢？下面代码有误，需要看看。
class Solution {
map <TreeNode*, TreeNode*> map;
set <TreeNode*> set;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root);
while(p != null)
{
set.add(p);//p也有可能是结果
p = map.find(p);
}
while(q != null)
{
if(set.contains(q))
return q;
q = map.find(q);
}
return null;
}
void dfs(TreeNode* root)
{
if(root->left != null)
{
map.put(root->left, root);//当根节点的左孩子不为空时，把左孩子放进哈希表
dfs(root->left);//继续递归
}
if(root.right != null)
{
map.put(root->right, root);
dfs(root->right);
}
}
}
解题思路4——LC官方题解
vector<TreeNode*> getPath(TreeNode* root, TreeNode* target)
{
vector<TreeNode*> path;
TreeNode* node = root;
while(node != target)
{
path.push_back(node);
if(target->val < node->val)
{
node = node->left;
}
else
{
node = node->right;
}
}
path.push_back(node);
return path;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
vector<TreeNode*> path_p = getPath(root, p);
vector<TreeNode*> path_q = getPath(root, q);
TreeNode* ancestor;
for(int i = 0; i < path_p.size() && i < path_q.size(); i++)
{
if(path_p[i] == path_q[i])
{
ancestor = path_p[i];
}
else
{
break;
}
}
return ancestor;
}
235题——二叉树的公共祖先
原题链接在这里：力扣235题——二叉树的公共祖先
解题思路
首先还是用递归的思想解决问题，
代码如下
TreeNode* res;
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(!root) return false;
bool lchild = dfs(root->left, p, q);
bool rchild = dfs(root->right, p, q);
if((lchild && rchild) || ((root->val == p->val || root->val == q->val) && (lchild || rchild)))
{
res = root;
}
return lchild || rchild || (root->val == p->val || root->val == q->val);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
dfs(root, p, q);
return res;
}
