算法题14 最低公共祖先

题目

　　给定一棵树，同时给出树中的两个结点(n1和n2)，求它们的最低公共祖先。

分析1

　　最直观的想法是判断某节点的左子树和右子树如果分别包含一个节点n1或n2，也就是一边一个，那该节点就是他们的最低公共祖先。可以用递归的方式依次判断左右子树求解

代码

 1 TreeNode* FirstCommonParent2(TreeNode* root,char a,char b)
 2 {
 3     if(root->value==a||root->value==b)
 4     {
 5         return root;
 6     }
 7 
 8     TreeNode* left,right;
 9     if (root->pLeft)
10     {
11         left=FirstCommonParent2(root->pLeft,a,b);
12     }
13     if (root->pRight)
14     {
15         right=FirstCommonParent2(root->pRight,a,b);
16     }
17 
18     if (left&&right)
19     {
20         return root;
21     } 
22 
23     return (left)?left:right;
24 }

分析2

　　如果将根节点到给出的两个节点的路径找到，然后就可以求两条路径的最后一个公共节点了。查找一个节点的路径可以用递归的方式实现

 1 ListNode* PrintPath1(TreeNode* root,char c)
 2 {
 3     if (root->value==c)
 4     {
 5         ListNode* node=new ListNode();
 6         node->value=c;
 7         node->pNext=NULL;
 8         return    node;
 9     }
10     ListNode* left=NULL;
11     ListNode* right=NULL;
12     if (root->pLeft)
13         left=PrintPath1(root->pLeft,c);
14     if (root->pRight)
15         right=PrintPath1(root->pRight,c);
16 
17     if (left||right)
18     {
19         ListNode* node=new ListNode();
20         node->value=root->value;
21         node->pNext=(left)?left:right;
22         return node;
23     }
24 
25     return NULL;
26 }

 1 void FirstCommonParent(TreeNode* root,char a,char b)
 2 {
 3     if(root==NULL)
 4     {
 5         return;
 6     }
 7 
 8     ListNode* list1=PrintPath1(root,a);
 9     ListNode* list2=PrintPath1(root,b);
10 
11     ListNode* node;
12     while (list1&&list2&&list1->value==list2->value)
13     {
14         node=list1;
15         list1=list1->pNext;
16         list2=list2->pNext;
17     }
18     cout<<node->value<<endl;
19 }