剑指offer第五十题:树中两个结点的最低公共祖先:这里的树是普通树,且没有指向父结点的指针。
//============================================================================
// Name : JZ-C-50.cpp
// Author : Laughing_Lz
// Version :
// Copyright : All Right Reserved
// Description : 树中两个结点的最低公共祖先:这里的树是普通树,且没有指向父结点的指针。
//============================================================================
#include
#include
#include "Tree.h"
#include
using namespace std;
using namespace std;
/**
* 获得从树的根结点到某结点的路径
*/
bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list& path) {
if (pRoot == pNode)
return true;
path.push_back(pRoot);
bool found = false;
vector::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& path1,
const list& path2) {
list::const_iterator iterator1 = path1.begin();
list::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 path1;
GetNodePath(pRoot, pNode1, path1);
list 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");
else
printf("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 main(int argc, char** argv) {
Test1();
Test2();
Test3();
Test4();
return 0;
}