剑指offer面试题：求树中两个结点的最低公共祖先

川长思鸟来 2022-07-28 08:36 134阅读 0赞

面试题：求树中两个结点的最低公共祖先

分析：

1）先讨论树是二叉树的情况，如果树是二叉树，并且是二叉搜索树，是可以找到公共祖先的，解法如下：

![Center][]

2)如果这棵树不是二叉搜索树，甚至连二叉树都不是，只是一颗普通的树，树中结点有指向父结点的指针，解法如下：

![Image 1][]

![Center 1][]

3）如果这棵树是普通的树，而且树中结点没有指向父结点的指针，解法如下：

![Center 2][]

![Center 3][]

4）解法3）中，需要对同一个结点重复遍历很多次，效率较低，如果允许使用辅助内存，则可以有效率更高的方法，解法如下：

![Center 4][]

![Center 5][]

![Center 6][]

![Center 7][]

![Center 8][]

可以根据这种思路写出C/C++代码，代码如下：

//该函数用来得到从根结点pRoot开始到达结点pNode的路径，这条路径存放在path中  
bool GetNodePath(TreeNode\* pRoot, TreeNode\* pNode, list<TreeNode\*>&path)  
\{

\}  
//该函数用来得到两个路径path1和path2的最后一个公共结点  
TreeNode\* GetLastCommonNode  
\{  
  
\}  
//该函数先调用GetNodePath 得到pRoot到达pNode1的路径path1,再得到pRoot到达pNode2的  
//path2,接着调用GetLastCommonPath得到path1和path2的最后一个公共结点，即我们要找的  
//最低公共祖先  
TreeNode \* GetLastCommonParent(TreeNode\* pRoot, TreeNode\* pNode1, TreeNode\* pNode2)  
\{  
  
\}

待续。。。

[Center]: /images/20220727/967add39424343dabdca700271ebeeee.png
[Image 1]: 
[Center 1]: /images/20220727/bbccdf36b2fb43d0914db6291a70f4e8.png
[Center 2]: /images/20220727/b5bd886bc9114eeba75bc80f54ecfda4.png
[Center 3]: /images/20220727/7d8d142efe2040da9a5c3e8cfdd62044.png
[Center 4]: /images/20220727/73ee46ecab3e43bf8b4d05a8b1ee6e54.png
[Center 5]: /images/20220727/6d8fb04c60ca4d0e97fe1ef2a010701e.png
[Center 6]: /images/20220727/3dd2a6d85d3d4ce6881048c8c2d79465.png
[Center 7]: /images/20220727/d1c5614fd5a948f5b0d797de39c22e71.png
[Center 8]: /images/20220727/e5d438a2d7b64d108e6b3d6c538f10fb.png