算法-二叉树篇22-二叉搜索树的最近公共祖先

二叉搜索树的最近公共祖先

力扣题目链接

题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 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; } }; 总结

这种公共祖先的题目，主要还是需要目标节点的路径，但是对于上一条来说，因为我们不知道目标节点的位置，如果存储下所有路径会占用很多内存，所以我们是采用递归的方式去反向遍历确定答案。这道题由于我们可以知道寻找目标节点的正确路径，所以我们可以直接存下该路径，减少了程序运行时不必要的时间开销。