二叉树-最近的公共祖先
已知二叉树，求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u，满足在树上最低(离根最 远)，且v,w两个节点都是u的子孙。 LeetCode 236. Lowest Common Ancestor of a Binary Tree
思考与分析
1.两个节点的公共祖先一定在从根节点，至这两个节点的路径上。 2.由于求公共祖先中的最近公共祖先，那么即同时出现在这两条路 径上的离根节点最远的节点(或离两个最近)。 3.最终算法即:求p节点路径，q节点路径，两路径上最后一个相同 的节点。
从根节点到某节点路径（深度搜索） 1.从根节点遍历(搜索)至该节点，找到该节点后就结束搜索。 2.将遍历过程中遇到的节点按照顺序存储起来，这些节点即路径节点。 前序遍历（深度优先）
void preorder(TreeNode *node, TreeNode *search){
if(!node){
return;
}
if(node == search){
}
preorder(node->left,search);
preorder(node->right,search);
}
求根节点至某节点路径
void preorder(TreeNode *node,TreeNode *search, std::vector<TreeNode*> &path,std::vector<TreeNode*> &result,int &finish)//node 正在遍历节点，search待搜索节点，path 遍历时节点路径栈，result 最终搜索到节点search的路径结果，finish 记录是否找到节点search的遍历，未找到时是0，找到为1{
if(!node || finish){
return;//当node为空或已找到search 节点直接返回，结束搜索
}
path.push_back(node);//先序遍历时，将节点压入path栈
if(node == search){
finish = 1;
result = path;
}
preorder(node->left,search,path,result,finish);
preorder(node->right,search,path,result,finish);
path.pop_back();//结束遍历node时，将node节点弹出path栈
}1.求出较短路径的长度n。 2.同时遍历p节点的路径与q节点的路径，遍历n个节点，最后一个相同节点，即最近 公共祖先。
class Solution{
public:
TreeNode* lowestCommonAncestor(TreeNode * root, TreeNode *p ,TreeNode *q){
std::vector<TreeNode*> path;申明遍历用的临时栈
std::vector<TreeNode*> node_p_path;//储存P节点路径
std::vector<TreeNode*>node_q_path;//储存q节点路径
int finish = 0;//记录是否完成搜索
preorder(root, p,path,node_p_path,finish);
path.clear();//清空path，finish,计算q节点路径
finish = 0;
preorder(root, q, path,node_q_path,finish);
int path_len = 0;
if(node_p_path.size() < node_q_path.size()){
path_len = node_p_path.size();
}
else{
path_len = node_q_path.size();
}
TreeNode * result = 0;
for (int i = 0; i < path_len; i++){
if(node_p_path[i] = node_q_path[i]){
result = node_p_path[i];
}//最后相同的节点为最近公共节点
}
return result;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.04.30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录