树：树中两个节点的最低公共祖先

问题：

　　求树中两个节点的公共祖先。

可能情况1：树为二叉搜索树。

　　我们可以从根节点开始搜索，如果当前节点的值比两个节点的值都大，那么下一步遍历左子树。

　　如果当前节点的值比两个节点的值都小，那么下一步遍历右子树。

　　如果当前节点的值比一个节点大，比另一个节点小，那么当前节点就是最低公共祖先节点。

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 
 4 struct TreeNode        // 树的节点定义
 5 {
 6     int val;
 7     TreeNode* left;
 8     TreeNode* right;
 9 };
10 
11 TreeNode* LCA_search1(TreeNode* proot, int nodea, int nodeb)
12 {
13     if(proot == nullptr)
14         return nullptr;
15     
16     if( proot->val > std::max(nodea, nodeb) )
17     {
18         return LCA_search1(proot->left, nodea, nodeb);
19     }
20     else if( proot->val < std::min(nodea, nodeb) )
21     {
22         return LCA_search1(proot->right, nodea, nodeb);
23     }
24     else
25     {
26         return proot;
27     }
28 }

可能情况2：树的节点中有指向父节点的指针

　　有了父节点指针，我们可以在两个待查找的节点向上搜索，相当于查找两个链表的第一个公共节点。

可能情况3：树不是二叉搜索树，也没有指向父节点的指针

　　从根节点开始进行dfs搜索，分别找到到达这两个节点的路径，这两条路径的最后一个公共节点就是最低公共祖先。

代码：

 1 struct TreeNode
 2 {
 3     int val;
 4     TreeNode *left;
 5     TreeNode *right;
 6 };
 7 
 8 TreeNode *LCA_search2(TreeNode* proot, TreeNode *nodea, TreeNode *nodeb)
 9 {
10     if(proot == nullptr || proot == nodea || proot == nodeb)
11         return proot;
12     
13     TreeNode *left = LCA_search2(proot->left, nodea, nodeb); // 找左子树是否存在nodea和nodeb
14     
15     TreeNode *right = LCA_search2(proot->right, nodea, nodeb);
16     
17     if(left && right)
18         return root;
19     else
20         return left ? left : right;
21 }