在上一篇文章中我們用的是暴力的遍歷判斷的方法，然而在樹有關(guān)的題目中罪裹，保存路徑也是一個很常用的思路饱普，比如求兩個節(jié)點的最短路徑，求路徑長度状共。
并且為了改善算法的復雜度套耕，我們可以嘗試減少遍歷的次數(shù)，上一種方法中峡继，我們遍歷了兩次冯袍，這次，我們試著保存遍歷的路徑碾牌，然后求兩個路徑的公共節(jié)點康愤。
首先我們有一個getNodePath 函數(shù)，該函數(shù)會將從頭結(jié)點到給定節(jié)點的路徑保存舶吗，然后有一個lastCommonNode函數(shù)求路徑的公共節(jié)點征冷。
首先我們看這個函數(shù)，這個函數(shù)的設計的思路值得我學習誓琼。
- 返回量：該函數(shù)返回的是布爾型變量检激，表示該節(jié)點是否在包含指定node的路徑上。
為什么要如此選取呢腹侣？為什么不直接返回一個list的指針叔收？我們要通過這個函數(shù)得到list，為什么要作為一個參數(shù)傳進去而不是作為返回量傲隶？
我們看函數(shù)的結(jié)構(gòu)饺律，和大多數(shù)遍歷樹的函數(shù)一樣，該函數(shù)也是遞歸的伦籍。我們的參數(shù)之一是樹的根節(jié)點蓝晒，意思是從這個節(jié)點往下遍歷。
整個函數(shù)有四個分支帖鸦，分別是
1芝薇，該根節(jié)點就是要找的節(jié)點，返回true
2作儿，否則在左子樹尋找
3洛二，否則在右子樹尋找
4，要找的節(jié)點不在當前根節(jié)點的下面攻锰。此時刪除掉路徑中存儲的當前節(jié)點晾嘶。
由此，我們遍歷整個樹之后留下 的節(jié)點就是路徑
bool getNodePath(node* ptree, node* pnode,std::list<node*>& path)
{
if (ptree == pnode)
return true;
path.push_back(ptree);
//在遞歸中娶吞，我們只關(guān)心這一輪要處理的節(jié)點垒迂，因此只需要把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;
}
由于我對遞歸函數(shù)還是不太熟悉，在設想的時候總是會在左右子樹分支的函數(shù)里面加上path.push_back(tree->left) 妒蛇，總是覺得處理當前節(jié)點就要有顯式的語句机断，但是實際上后面的遞歸調(diào)用會把這個節(jié)點加進去的，如果還寫绣夺，那就是重復了吏奸。
在遞歸的函數(shù)中我們應該這樣想，我們只處理當前節(jié)點陶耍，當前節(jié)點的子節(jié)點留給遞歸就行了奋蔚。
下面是完整的函數(shù)：
//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);
//在遞歸中，我們只關(guān)心這一輪要處理的節(jié)點烈钞，因此只需要把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);
}
文章參考何海濤大神文章
