二叉搜索樹的最近公共祖先
力扣題目鏈接
題目描述
給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”
解題思路
這道題完全可以套上一題的答案，所以這里我就寫了一個更加體現出二叉搜索樹的答案。
感興趣的可以看上一題算法-二叉樹篇21-二叉樹的最近公共祖先
大致步驟如下：
- 首先確定借助二叉搜索樹的特性來解決，那么我們需要一個尋找目標節點的方法，這方法傳入根節點和目標節點；
- 然后根據目標節點和根節點的大小關系向下遍歷，直到尋找到該節點；
- 在尋找的過程中，把遍歷過的節點存入隊列中，然后返回；
- 主函數中，我們得到了兩個節點的路徑隊列，然后尋找兩個隊列最后一個相等的節點，就是答案。
題解
class Solution {
public:queue<TreeNode*> find(TreeNode* root, TreeNode* p){queue<TreeNode*> ans;ans.push(root);TreeNode* cur = root;while(cur != p){if(cur->val > p->val){cur = cur->left;}else {cur = cur->right;}ans.push(cur);}return ans;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {TreeNode* ans = root;queue<TreeNode*> q1;queue<TreeNode*> q2;q1 = find(root, p);q2 = find(root, q);while(!q1.empty() && !q2.empty()){if(q1.front() == q2.front()){ans = q1.front();q1.pop();q2.pop();}else {break;}}return ans;}
};
總結
這種公共祖先的題目，主要還是需要目標節點的路徑，但是對于上一條來說，因為我們不知道目標節點的位置，如果存儲下所有路徑會占用很多內存，所以我們是采用遞歸的方式去反向遍歷確定答案。這道題由于我們可以知道尋找目標節點的正確路徑，所以我們可以直接存下該路徑，減少了程序運行時不必要的時間開銷。
)
