算法|二叉树二叉树最近公共祖先算法|Leetcode

给定一颗二叉搜索树 2个节点，求2个节点的最近公共祖先
思路：

如果2个节点均大于根节点的值，那递归在右子树寻找
如果2个节点均小于根节点的值，那递归在左子树寻找
如果刚好一大一小于根节点的值，那么返回该根节点

Node* Get(Node* root,Node* p1,Node* p2) { if(root==NULL || p1==NULL || p2==NULL)//指针检查 { return NULL; } int data_root=root->data; int data_p1=p1->data; int data_p2=p2->data; if(data_p1<=data_root && data_p2<=data_root) { return Get(root->left); } else if(data_p1>data_root && data_p2>data_root) { return Get(root->right); } else { return root; } }

若是一般的普通二叉树，求解其最近的公共祖先。（保证测试数据合法）
思路：采取前序遍历的方式，对于当前的节点，分别返回左右子树包含的目标节点数
【算法|二叉树二叉树最近公共祖先】若left_num==right_num=1即当前节点的左右子树各含有一个目标节点，那么当前节点为最近公共祖先。
其他一般情况下，返回当前树的目标节点数，若当前节点为目标节点，那么返回1

int dfs(Node* now,node* one, node* two,node*& res) { if(now==one || now==two) { return 1; } int left_count=0,right_count=0; if(now->left!=NULL) left_count=dfs(now-left,one,two,res); if(left_count==2)//及时返回，一旦找到结果，那么立即返回 return 2; if(now->right!=NULL) right_count=dfs(now->right,one,two,res); if(left_count==right_count==1) //刚好左右各有一个那么结果为当前节点 { res=now; return 2; } return left_count+right_count; }