解析：先序遍歷樹，用兩個鏈表保存遍歷所走的路徑，再求兩個鏈表的最低公共結點

#include <stdio.h> #include <vector> #include <iostream>using namespace std;typedef struct node {char var;struct node* lTree;struct node* rTree; }Tree;Tree* create(void) {char ch;scanf("%c",&ch);if(ch=='#')return NULL;Tree* node;node=(Tree*)malloc(sizeof(Tree));node->var=ch;node->lTree=create();node->rTree=create();return node; }void preorder(Tree* root) {if(root==NULL)return;else{printf("%c\t",root->var);preorder(root->lTree);preorder(root->rTree);} }bool findPath(Tree* root,Tree* node,vector<Tree*> &path) {if(root==NULL)return false;if(root->var == node->var)return true;bool result=false;path.push_back(root);if(!result){result=findPath(root->lTree,node,path);if(!result)result=findPath(root->rTree,node,path);}if(result==false)path.pop_back();return result; }Tree* commonNode(vector<Tree*> path1,vector<Tree*> path2) {vector<Tree*>::iterator i1=path1.begin();vector<Tree*>::iterator i2=path2.begin();while(*i1 == *i2){i1++;i2++;}return *(--i1); }Tree* lastCommonNode(Tree* root,Tree* node1,Tree* node2) {if(root==NULL || node1==NULL || node2==NULL)return NULL;vector<Tree*> path1;vector<Tree*> path2;findPath(root,node1,path1);/*vector<Tree*>::iterator i=path1.begin();for(;i!=path1.end();i++)cout<<(*i)->var<<endl;*/findPath(root,node2,path2);/*vector<Tree*>::iterator i=path2.begin();for(;i!=path2.end();i++)cout<<(*i)->var<<endl;*/return commonNode(path1,path2); }int main() {Tree* root;root=create();//preorder(root);//cout<<endl;Tree* node1;node1=(Tree*)malloc(sizeof(Tree));node1->var='f';node1->lTree=NULL;node1->rTree=NULL;Tree* node2;node2=(Tree*)malloc(sizeof(Tree));node2->var='h';node2->lTree=NULL;node2->rTree=NULL;Tree* node;node=lastCommonNode(root,node1,node2);cout<<node->var<<endl;return 0; }

總結

以上是生活随笔為你收集整理的剑指offer 算法（树的两个节点的最低祖先）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。