ITeye博客

MuchContact的博客

MuchContact · 共 1 篇文章

[置顶] 利用前后序遍历求解树中两个节点的最低公共节点

问题: 求树种任意两个节点的最低公共节点 常见的解法是求解节点到根的路径,对路径做比对。参见: http://gaotong1991.iteye.com/blog/2042770 下面来介绍另外一种方法求解。 准备: 1、什么是最低公共节点? 答: https://en.wikipedia.org/wiki/Lowest_common_ancestor 2、最低公共节点有哪些方面需要注意? **答:**按照两个节点是否存在一个节点(设为A)是以另外一个节点(设为B)为根的子树中,分为两种情况: 是 意味着A和B在B的一个分支下,返回B即可。 否 意味着A和B肯定在公共节点的不同分支下,可以按…

2014-09-06 22:34 · 数据结构与算法 · 评论(1)