在上一篇文章中我们用的是暴力的遍历判断的方法，然而在树有关的题目中，保存路径也是一个很常用的思路，比如求两个节点的最短路径，求路径长度。
并且为了改善算法的复杂度，我们可以尝试减少遍历的次数，上一种方法中，我们遍历了两次，这次，我们试着保存遍历的路径，然后求两个路径的公共节点。
首先我们有一个getNodePath 函数，该函数会将从头结点到给定节点的路径保存，然后有一个lastCommonNode函数求路径的公共节点。
首先我们看这个函数，这个函数的设计的思路值得我学习。
- 返回量：该函数返回的是布尔型变量，表示该节点是否在包含指定node的路径上。
为什么要如此选取呢？为什么不直接返回一个list的指针？我们要通过这个函数得到list，为什么要作为一个参数传进去而不是作为返回量？
我们看函数的结构，和大多数遍历树的函数一样，该函数也是递归的。我们的参数之一是树的根节点，意思是从这个节点往下遍历。
整个函数有四个分支，分别是
1，该根节点就是要找的节点，返回true
2，否则在左子树寻找
3，否则在右子树寻找
4，要找的节点不在当前根节点的下面。此时删除掉路径中存储的当前节点。
由此，我们遍历整个树之后留下 的节点就是路径
bool getNodePath(node* ptree, node* pnode,std::list<node*>& path)
{
if (ptree == pnode)
return true;
path.push_back(ptree);
//在递归中，我们只关心这一轮要处理的节点，因此只需要把ptree放进去而不需要在left和right中加入push_back
bool found = false;
if (ptree->lnode)
{
found = getNodePath(ptree->lnode, pnode, path);
}
if (!found&&ptree->rnode)
{
found = getNodePath(ptree->rnode, pnode, path);
}
if (!found)
path.pop_back();
return found;
}
由于我对递归函数还是不太熟悉，在设想的时候总是会在左右子树分支的函数里面加上path.push_back(tree->left) ，总是觉得处理当前节点就要有显式的语句，但是实际上后面的递归调用会把这个节点加进去的，如果还写，那就是重复了。
在递归的函数中我们应该这样想，我们只处理当前节点，当前节点的子节点留给递归就行了。
下面是完整的函数：
//way2,get the path , the get the last common node of two paths
#include <list>
bool getNodePath(node* ptree, node* pnode,std::list<node*>& path)
{
if (ptree == pnode)
return true;
path.push_back(ptree);
//在递归中，我们只关心这一轮要处理的节点，因此只需要把ptree放进去而不需要在left和right中加入push_back
bool found = false;
if (ptree->lnode)
{
found = getNodePath(ptree->lnode, pnode, path);
}
if (!found&&ptree->rnode)
{
found = getNodePath(ptree->rnode, pnode, path);
}
if (!found)
path.pop_back();
return found;
}
node* lastCommonNode_l(std::list<node*>& path1, std::list<node*>& path2)
{
node* path = NULL;
std::list<node*>::const_iterator ptr1=path1.begin();
std::list<node*>::const_iterator ptr2 = path2.begin();
while (ptr1 != path1.end() && ptr2 != path2.end())
{
if (*ptr1 == *ptr2)
path = *ptr1;//why *ptr
//we do not return here since we need the last common node
ptr1++;
ptr2++;
}
return path;//attention
}
node* LastCommonNode(node* tree, node* node1, node* node2)
{
if (tree == NULL || !node1 || node2)
return;
std::list<node*> path1;
std::list<node*> path2;
getNodePath(tree, node1, path1);
getNodePath(tree, node1, path2);
return lastCommonNode_l(path1, path2);
}
文章参考何海涛大神文章
网友评论