杂谈：在网上 看到 这个 题目，忍不住 自己 操作了 一把。 呵呵。兴趣 是 最好的 老师。
网上的 解决方案 五花八门，其中 比较 好 理解的 思路 就是 求出 两个节点 的 所有祖先。然后 比较 祖先，，求出 最近祖先。
下面 的 两个方案 都是 这套 思路，但是 在 求 两个节点的所有祖先 这个问题上 不同；
第一种 方案 是 递归 求出 节点的 祖先。
第二种 是 后序遍历查找 节点，找到 节点后 退出遍历，这时 栈中 保留的 节点 就是 这个节点的 祖先。
第一种 方案 思路 解析，并且 在 比较祖先问题上的 时间 复杂度 为 O(Max(节点1祖先数，节点2祖先数）。
第二种 方案 操作 复杂，在 比较 祖先 问题上的 时间 复杂度 为 O(节点1祖先树 * 节点2祖先数）。
所以推荐 第一种
下面 上代码：
欢迎指出 代码 不足：
完整代码地址：
// binaryTree.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <cstdlib>#include "stack.h"#include "queue.h"#include <math.h>typedef int ElementType;typedef struct TreeNode{ElementType data;TreeNode * leftChild;TreeNode * rightChild;} * Tree;void treeInit(Tree * tree){*tree = NULL;}//其实 自己 不懂 这个 函数 初始化…E_State treeCreate(Tree *tree){ElementType data;scanf("%d",&data);if (data == 0){*tree = NULL;}else{*tree = (Tree)malloc(sizeof(TreeNode));(*tree)->data = data;treeCreate(&(*tree)->leftChild);treeCreate(&(*tree)->rightChild);}return E_State_Ok;}//后序遍历void treeClear(Tree * tree){if (tree != NULL){if ((*tree)->leftChild != NULL){treeClear(&(*tree)->leftChild);}else if((*tree)->rightChild != NULL){treeClear(&(*tree)->rightChild);}free(*tree);*tree = NULL;}}void treeDestory(Tree * tree){treeClear(tree);}//递归算法 先序void preOrderTraverse(Tree tree){if (tree != NULL){printf("%d\t",tree->data);preOrderTraverse(tree->leftChild);preOrderTraverse(tree->rightChild);}}//查找最近祖先 方法1//查找祖先 bool treeGetAllParent(Tree tree,ElementType data,linkStack &stack){if (tree != NULL){if (tree->data == data){return true;}if (treeGetAllParent(tree->leftChild,data,stack) || treeGetAllParent(tree->rightChild,data,stack)){stackPush(&stack,tree);return true;}}return false;}Tree treeFindCommonAncestor1(Tree tree,ElementType data1,ElementType data2){linkStack stack1;stackInit(&stack1);treeGetAllParent(tree,data1,stack1);//查找 data1 的所有祖先..linkStack stack2;stackInit(&stack2);treeGetAllParent(tree,data2,stack2);//查找 data2 的所有祖先..Tree commonAncestor = NULL;//时间复杂度为 ： o(max(stackLen(stack1),stackLen(stack2))while (!stackEmpty(stack1) && !stackEmpty(stack2))//{Tree father1,father2;stackPop(&stack1,&father1);stackPop(&stack2,&father2);if (father1 == father2){commonAncestor = father1;}else{break;}}stackDestory(&stack1);stackDestory(&stack2);return commonAncestor;}//寻找节点child1 和 child2 的最近 共同祖先//后序遍历 子树//为了方便 没有 写 子树，而是写 数据，在测试中 数据 不重复…// 辅助函数 ， 查找 节点的 祖先 并保存在栈中//原理：后序遍历void treeFindParentStack(Tree tree,ElementType data,linkStack & stack){Tree pre = NULL;//上一次访问的节点Tree cur = tree;//当前节点//后序遍历while(cur || !stackEmpty(stack)){while (cur != NULL)//寻找 最左下角的节点{while (cur != NULL){stackPush(&stack,cur);cur = cur ->leftChild;}stackGetTop(stack,&cur);//然后寻找 右子树 最左下角的节点cur = cur ->rightChild;}bool isFind = false;while (!stackEmpty(stack))//访问，并判断从左子树返回，还是从右子树返回{stackPop(&stack,&cur);//找到了某个节点，或者 到达了 根节点，遍历结束if (cur->data == data || cur == tree){isFind = true;break;}pre = cur;stackGetTop(stack,&cur);if (cur->leftChild == pre)//从左子树返回的 退出循环，继续查访 右子树.{cur = cur->rightChild;break;}//从右子树访问的继续退栈..}if (isFind)//找到了节点。。{break;}}}//思路：找到 两个节点的 祖先，然后 求出 最近祖先.Tree treeFindCommonAncestor2(Tree tree,ElementType data1,ElementType data2){linkStack stack1;stackInit(&stack1);treeFindParentStack(tree,data1,stack1);linkStack stack2;stackInit(&stack2);treeFindParentStack(tree,data2,stack2);Tree commonAncestor = NULL;//时间复杂度 O(stackLen(stack1) * stackLen(stack2))while (!stackEmpty(stack1))//{Tree father1;stackPop(&stack1,&father1);linkStack copy = stackCopy(&stack2);while (!stackEmpty(copy)){Tree father2;stackPop(©,&father2);if (father1 == father2){commonAncestor = father1;break;}}stackDestory(©);if (commonAncestor != NULL){break;}}stackDestory(&stack1);stackDestory(&stack2);return commonAncestor;//没有最近祖先..}//打印最近祖先void printCommonAncestor(Tree commonAncestor,ElementType data1,ElementType data2){if (commonAncestor){printf("%d 和 %d 的 最近祖先是：%d\n",data1,data2,commonAncestor->data);}else{printf("%d 和 %d 无祖先\n",data1,data2);}}int _tmain(int argc, _TCHAR* argv[]){Tree tree;printf("—————创建树（先序,0代表子树为空）—————–\n");treeCreate(&tree);printf("————先序递归遍历—————-\n");preOrderTraverse(tree);printf("————寻找最近祖先方法1—————-\n");int data1 = 4,data2 = 7;Tree commonAncestor = treeFindCommonAncestor1(tree,data1,data2);printCommonAncestor(commonAncestor,data1,data2);data1 = 5;data2 = 10;commonAncestor = treeFindCommonAncestor1(tree,data1,data2);printCommonAncestor(commonAncestor,data1,data2);data1 = 6;data2 = 11;commonAncestor = treeFindCommonAncestor1(tree,data1,data2);printCommonAncestor(commonAncestor,data1,data2);printf("————寻找最近祖先方法2—————-\n");data1 = 4;data2 = 7;commonAncestor = treeFindCommonAncestor2(tree,data1,data2);printCommonAncestor(commonAncestor,data1,data2);data1 = 5;data2 = 10;commonAncestor = treeFindCommonAncestor2(tree,data1,data2);printCommonAncestor(commonAncestor,data1,data2);data1 = 6;data2 = 11;commonAncestor = treeFindCommonAncestor2(tree,data1,data2);printCommonAncestor(commonAncestor,data1,data2);treeDestory(&tree);return 0;}
特别说明：linkStack 代码 在以前的 链栈 的文章中 可以找到，并且 增加 stackCopy 函数：
会让你的心态更平和更坦然，
