怎么才能找到想做网站建设的客源,房地产新闻最新政策,题库网站怎样做,遵化建设局网站二叉搜索树的最近公共祖先
力扣题目链接
题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个结点 p、q#xff0c;最近公共祖先表示为一个结点 x#xff0c;满足 x 是 p、q 的祖先且…二叉搜索树的最近公共祖先
力扣题目链接
题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
解题思路
这道题完全可以套上一题的答案所以这里我就写了一个更加体现出二叉搜索树的答案。 感兴趣的可以看上一题算法-二叉树篇21-二叉树的最近公共祖先
大致步骤如下
首先确定借助二叉搜索树的特性来解决那么我们需要一个寻找目标节点的方法这方法传入根节点和目标节点然后根据目标节点和根节点的大小关系向下遍历直到寻找到该节点在寻找的过程中把遍历过的节点存入队列中然后返回主函数中我们得到了两个节点的路径队列然后寻找两个队列最后一个相等的节点就是答案。
题解
class Solution {
public:queueTreeNode* find(TreeNode* root, TreeNode* p){queueTreeNode* 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;queueTreeNode* q1;queueTreeNode* 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;}
};总结
这种公共祖先的题目主要还是需要目标节点的路径但是对于上一条来说因为我们不知道目标节点的位置如果存储下所有路径会占用很多内存所以我们是采用递归的方式去反向遍历确定答案。这道题由于我们可以知道寻找目标节点的正确路径所以我们可以直接存下该路径减少了程序运行时不必要的时间开销。
