本文主要是介绍案例二 树中两个结点的最低公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题: 树中两个结点的最低公共祖先.
(1)是一颗二叉树，并且是二叉搜素树（根据二叉搜素树的性质求解）
(2)普通树中结点有指向父结点的指针(演变为两个链表求解第一个公共结点)
(3)一棵普通的树，树中的结点没有指向父结点的指针(最复杂的情况)
通用的解法如下:
//记录结点的路径
bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>& path)
{if(pRoot == pNode)return true;path.push_back(pRoot);bool found = false;vector<TreeNode*>::iterator i = pRoot->m_vChildren.begin();while(!found && i < pRoot->m_vChildren.end()){found = GetNodePath(*i, pNode, path);++i;}if(!found)path.pop_back();return found;
}TreeNode* GetLastCommonNode( const list<TreeNode*>& path1, const list<TreeNode*>& path2)
{list<TreeNode*>::const_iterator iterator1 = path1.begin();list<TreeNode*>::const_iterator iterator2 = path2.begin();TreeNode* pLast = NULL;while(iterator1 != path1.end() && iterator2 != path2.end()){if(*iterator1 == *iterator2)pLast = *iterator1;iterator1++;iterator2++;}return pLast;
}
//获取最低的公共父结点
TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
{if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)return NULL;list<TreeNode*> path1;GetNodePath(pRoot, pNode1, path1);list<TreeNode*> path2;GetNodePath(pRoot, pNode2, path2);return GetLastCommonNode(path1, path2);
}// ====================测试代码====================void Test(char* testName, TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2, TreeNode* pExpected)
{if(testName != NULL)printf("%s begins: \n", testName);TreeNode* pResult = GetLastCommonParent(pRoot, pNode1, pNode2);if((pExpected == NULL && pResult == NULL) || (pExpected != NULL && pResult != NULL && pResult->m_nValue == pExpected->m_nValue))printf("Passed.\n");elseprintf("Failed.\n");
}// 形状普通的树
// 1
// / \
// 2 3
// / \
// 4 5
// / \ / | \
// 6 7 8 9 10
void Test1()
{TreeNode* pNode1 = CreateTreeNode(1);TreeNode* pNode2 = CreateTreeNode(2);TreeNode* pNode3 = CreateTreeNode(3);TreeNode* pNode4 = CreateTreeNode(4);TreeNode* pNode5 = CreateTreeNode(5);TreeNode* pNode6 = CreateTreeNode(6);TreeNode* pNode7 = CreateTreeNode(7);TreeNode* pNode8 = CreateTreeNode(8);TreeNode* pNode9 = CreateTreeNode(9);TreeNode* pNode10 = CreateTreeNode(10);ConnectTreeNodes(pNode1, pNode2);ConnectTreeNodes(pNode1, pNode3);ConnectTreeNodes(pNode2, pNode4);ConnectTreeNodes(pNode2, pNode5);ConnectTreeNodes(pNode4, pNode6);ConnectTreeNodes(pNode4, pNode7);ConnectTreeNodes(pNode5, pNode8);ConnectTreeNodes(pNode5, pNode9);ConnectTreeNodes(pNode5, pNode10);Test("Test1", pNode1, pNode6, pNode8, pNode2);
}// 树退化成一个链表
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
void Test2()
{TreeNode* pNode1 = CreateTreeNode(1);TreeNode* pNode2 = CreateTreeNode(2);TreeNode* pNode3 = CreateTreeNode(3);TreeNode* pNode4 = CreateTreeNode(4);TreeNode* pNode5 = CreateTreeNode(5);ConnectTreeNodes(pNode1, pNode2);ConnectTreeNodes(pNode2, pNode3);ConnectTreeNodes(pNode3, pNode4);ConnectTreeNodes(pNode4, pNode5);Test("Test2", pNode1, pNode5, pNode4, pNode3);
}// 树退化成一个链表，一个结点不在树中
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
void Test3()
{TreeNode* pNode1 = CreateTreeNode(1);TreeNode* pNode2 = CreateTreeNode(2);TreeNode* pNode3 = CreateTreeNode(3);TreeNode* pNode4 = CreateTreeNode(4);TreeNode* pNode5 = CreateTreeNode(5);ConnectTreeNodes(pNode1, pNode2);ConnectTreeNodes(pNode2, pNode3);ConnectTreeNodes(pNode3, pNode4);ConnectTreeNodes(pNode4, pNode5);TreeNode* pNode6 = CreateTreeNode(6);Test("Test3", pNode1, pNode5, pNode6, NULL);
}// 输入NULL
void Test4()
{Test("Test4", NULL, NULL, NULL, NULL);
}int _tmain(int argc, _TCHAR* argv[])
{Test1();Test2();Test3();Test4();return 0;
}
这篇关于案例二 树中两个结点的最低公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
