文章目录
一、 二叉搜索树的最近公共祖先
1. 二叉搜索树的最近公共祖先
可以直接利用二叉搜索树的性质，从根节点开始访问，访问到节点的值在p和q之间则是最近公共祖先。
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
q = q > p ? q : p;
while(root != nullptr){
if(root->val >= p && root->val <= q){
return root->val;
}
else if(root->val < p){
root = root->right;
}
else{
root = root->left;
}
}
return -1;
}
};
2. 二叉树的最近公共祖先
- 存储父节点
我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
- 从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
- 从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
- 同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。
class Solution {
public:
unordered_map<int,TreeNode*> father;
unordered_map<int,bool> vis;
void dfs(TreeNode* root,TreeNode* pre){
if(root == nullptr) return;
father[root->val] = pre;
dfs(root->left,root);
dfs(root->right,root);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root,nullptr);
while(p != nullptr){
vis[p->val] = true;
p = father[p->val];
}
while(q != nullptr){
if(vis[q->val]){
return q;
}
q = father[q->val];
}
return nullptr;
}
};
时间复杂度O(n)，空间复杂度O(n)
- 递归
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || root == NULL) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) return root;
if (left == NULL) return right;
return left;
}
};
时间复杂度O(n)，空间复杂度O(n)
3. 从二叉树中找到两个节点的最近公共祖先
#include <unordered_map>
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
father[root->val] = nullptr;
dfs(root);
while(father[o1] != nullptr){
flag[o1] = true;
o1 = father[o1]->val;
}
while(father[o2] != nullptr){
if(flag[o2] == true) return o2;
o2 = father[o2]->val;
}
return o1;
}
private:
unordered_map<int, TreeNode*> father;
unordered_map<int, bool> flag;
void dfs(TreeNode* root) {
if(root->left){
father[root->left->val] = root;
dfs(root->left);
}
if(root->right){
father[root->right->val] = root;
dfs(root->right);
}
}
};
二、重建二叉树
1. 从先序和中序遍历序列构造二叉树
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
if (pre.size() < 1) return nullptr;
return reConstructBinaryTree(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
}
private:
TreeNode* reConstructBinaryTree(vector<int> pre, int i, int m, vector<int> vin,
int j, int n) {
if (i > m || j > n) return nullptr;
TreeNode* root = new TreeNode(pre[i]);
for (int index = j; index <= n; index++) {
if (vin[index] == pre[i]) {
root->left = reConstructBinaryTree(pre, i + 1, i + (index - j), vin, j,
index - 1);
root->right = reConstructBinaryTree(pre, i + (index - j) + 1, m, vin, index + 1,
n);
}
}
return root;
}
};
2. 从中序和后序遍历序列构造二叉树
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size() == 0) return nullptr;
return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
private:
TreeNode* buildTree(vector<int>& inorder, int i, int m, vector<int>& postorder, int j, int n){
if(i > m || j > n) return nullptr;
TreeNode* root = new TreeNode(postorder[n]);
for(int index = i; index <= m; ++index){
if(inorder[index] == postorder[n]){
root->left = buildTree(inorder, i, index - 1, postorder, j, j + (index - i - 1));
root->right = buildTree(inorder, index + 1, m, postorder, j + (index - i), n - 1);
}
}
return root;
}
};