JZ-C-50

桃扇骨 2021-12-18 14:59 270阅读 0赞

剑指offer第五十题：树中两个结点的最低公共祖先：这里的树是普通树，且没有指向父结点的指针。

1 //============================================================================
      2 // Name        : JZ-C-50.cpp
      3 // Author      : Laughing_Lz
      4 // Version     :
      5 // Copyright   : All Right Reserved
      6 // Description : 树中两个结点的最低公共祖先：这里的树是普通树，且没有指向父结点的指针。
      7 //============================================================================
      8 
      9 #include <iostream>
     10 #include <stdio.h>
     11 #include "Tree.h"
     12 #include <list>
     13 using namespace std;
     14 
     15 using namespace std;
     16 /**
     17  * 获得从树的根结点到某结点的路径
     18  */
     19 bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>& path) {
     20     if (pRoot == pNode)
     21         return true;
     22 
     23     path.push_back(pRoot);
     24 
     25     bool found = false;
     26 
     27     vector<TreeNode*>::iterator i = pRoot->m_vChildren.begin(); //这里的树为普通树，甚至不是二叉树。所以这里按照前序遍历子树即可。
     28     while (!found && i < pRoot->m_vChildren.end()) {
     29         found = GetNodePath(*i, pNode, path);
     30         ++i;
     31     }
     32 
     33     if (!found)
     34         path.pop_back();
     35 
     36     return found;
     37 }
     38 /**
     39  * 获得两条路径的最后一个公共结点。
     40  */
     41 TreeNode* GetLastCommonNode(const list<TreeNode*>& path1,
     42         const list<TreeNode*>& path2) {
     43     list<TreeNode*>::const_iterator iterator1 = path1.begin();
     44     list<TreeNode*>::const_iterator iterator2 = path2.begin();
     45 
     46     TreeNode* pLast = NULL;
     47 
     48     while (iterator1 != path1.end() && iterator2 != path2.end()) {
     49         if (*iterator1 == *iterator2)
     50             pLast = *iterator1; //遍历完两条路径，得到最后一个公共结点。
     51 
     52         iterator1++;
     53         iterator2++;
     54     }
     55 
     56     return pLast;
     57 }
     58 
     59 TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1,
     60         TreeNode* pNode2) {
     61     if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
     62         return NULL;
     63 
     64     list<TreeNode*> path1;
     65     GetNodePath(pRoot, pNode1, path1);
     66 
     67     list<TreeNode*> path2;
     68     GetNodePath(pRoot, pNode2, path2);
     69 
     70     return GetLastCommonNode(path1, path2);
     71 }
     72 
     73 // ====================测试代码====================
     74 
     75 void Test(char* testName, TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2,
     76         TreeNode* pExpected) {
     77     if (testName != NULL)
     78         printf("%s begins: \n", testName);
     79 
     80     TreeNode* pResult = GetLastCommonParent(pRoot, pNode1, pNode2);
     81 
     82     if ((pExpected == NULL && pResult == NULL)
     83             || (pExpected != NULL && pResult != NULL
     84                     && pResult->m_nValue == pExpected->m_nValue))
     85         printf("Passed.\n");
     86     else
     87         printf("Failed.\n");
     88 }
     89 
     90 // 形状普通的树
     91 //              1
     92 //            /   \
     93 //           2     3
     94 //       /       \
     95 //      4         5
     96 //     / \      / |  \
     97 //    6   7    8  9  10
     98 void Test1() {
     99     TreeNode* pNode1 = CreateTreeNode(1);
    100     TreeNode* pNode2 = CreateTreeNode(2);
    101     TreeNode* pNode3 = CreateTreeNode(3);
    102     TreeNode* pNode4 = CreateTreeNode(4);
    103     TreeNode* pNode5 = CreateTreeNode(5);
    104     TreeNode* pNode6 = CreateTreeNode(6);
    105     TreeNode* pNode7 = CreateTreeNode(7);
    106     TreeNode* pNode8 = CreateTreeNode(8);
    107     TreeNode* pNode9 = CreateTreeNode(9);
    108     TreeNode* pNode10 = CreateTreeNode(10);
    109 
    110     ConnectTreeNodes(pNode1, pNode2);
    111     ConnectTreeNodes(pNode1, pNode3);
    112 
    113     ConnectTreeNodes(pNode2, pNode4);
    114     ConnectTreeNodes(pNode2, pNode5);
    115 
    116     ConnectTreeNodes(pNode4, pNode6);
    117     ConnectTreeNodes(pNode4, pNode7);
    118 
    119     ConnectTreeNodes(pNode5, pNode8);
    120     ConnectTreeNodes(pNode5, pNode9);
    121     ConnectTreeNodes(pNode5, pNode10);
    122 
    123     Test("Test1", pNode1, pNode6, pNode8, pNode2);
    124 }
    125 
    126 // 树退化成一个链表
    127 //               1
    128 //              /
    129 //             2
    130 //            /
    131 //           3
    132 //          /
    133 //         4
    134 //        /
    135 //       5
    136 void Test2() {
    137     TreeNode* pNode1 = CreateTreeNode(1);
    138     TreeNode* pNode2 = CreateTreeNode(2);
    139     TreeNode* pNode3 = CreateTreeNode(3);
    140     TreeNode* pNode4 = CreateTreeNode(4);
    141     TreeNode* pNode5 = CreateTreeNode(5);
    142 
    143     ConnectTreeNodes(pNode1, pNode2);
    144     ConnectTreeNodes(pNode2, pNode3);
    145     ConnectTreeNodes(pNode3, pNode4);
    146     ConnectTreeNodes(pNode4, pNode5);
    147 
    148     Test("Test2", pNode1, pNode5, pNode4, pNode3);
    149 }
    150 
    151 // 树退化成一个链表，一个结点不在树中
    152 //               1
    153 //              /
    154 //             2
    155 //            /
    156 //           3
    157 //          /
    158 //         4
    159 //        /
    160 //       5
    161 void Test3() {
    162     TreeNode* pNode1 = CreateTreeNode(1);
    163     TreeNode* pNode2 = CreateTreeNode(2);
    164     TreeNode* pNode3 = CreateTreeNode(3);
    165     TreeNode* pNode4 = CreateTreeNode(4);
    166     TreeNode* pNode5 = CreateTreeNode(5);
    167 
    168     ConnectTreeNodes(pNode1, pNode2);
    169     ConnectTreeNodes(pNode2, pNode3);
    170     ConnectTreeNodes(pNode3, pNode4);
    171     ConnectTreeNodes(pNode4, pNode5);
    172 
    173     TreeNode* pNode6 = CreateTreeNode(6);
    174 
    175     Test("Test3", pNode1, pNode5, pNode6, NULL);
    176 }
    177 
    178 // 输入NULL
    179 void Test4() {
    180     Test("Test4", NULL, NULL, NULL, NULL);
    181 }
    182 
    183 int main(int argc, char** argv) {
    184     Test1();
    185     Test2();
    186     Test3();
    187     Test4();
    188 
    189     return 0;
    190 }

转载于:https://www.cnblogs.com/Laughing-Lz/p/5624847.html