LCA查找最近公共祖先算法笔记

参考大佬的思路
//AC code
/*
1:根据中序，先序建树
2: 用 findnode( )查看待查询节点是否存在
3:若待查询节点是存在,用 LCA( )查找最近公共祖先
其中LCA有三种：
u,v都在左子树或右子树,或者u,v分别在左子树和右子树，
因此可采取如下步骤：
(1)::判断当前遍历的节点是否为空，为空返回null，
(2)::节点数据域是否等于u，是否等于p，是的话返回当前节点。
(3)::之后判断left 和right是否为空，若都不为空，则当前root为祖先指针，
若其中一个为空，则返回另一边，为答案。
4:格式输出
*/

node *LCA(node *root, int u, int v) { //查找两节点最近祖先 if (root == NULL) return NULL; if (root->data=https://www.it610.com/article/= u || root->data=https://www.it610.com/article/= v) return root; node *left =LCA(root->lchild,u,v); node *right = LCA(root->rchild,u,v); if (left && right ) return root; //u,v分别位于左右子树的情况 return left == NULL ? right : left; } --------------------- 作者：菜多多来源：CSDN 原文：https://blog.csdn.net/qq_41317652/article/details/82557975 版权声明：本文为博主原创文章，转载请附上博文链接！

【LCA查找最近公共祖先】https://blog.csdn.net/qq_41317652/article/details/82557975