(017)将一棵二叉查找树重构成链表(keep it up)

给定一棵二叉查找树,设计算法,将每一层的全部结点构建为一个

链表(也就是说, 假设树有D层,那么你将构建出D个链表).

这个题实质是个BFS,可是实现起来有点麻烦,又不像常见的BFS,

所以编写代码时有点艰难。

以下的代码使用两个list来实现层次遍历的,首先用Cur链表存储当前层

的结点,然后用Pre链表存储当前层的子层结点,Cur和Pre。下一次遍历时

Pre就变成当前层,Cur就变成它的子层。这样交替运行。

代码:

struct TreeNode
{
int data;
TreeNode* leftChild;
TreeNode* rightChild;
}; void createLinks(const TreeNode* vRoot, std::vector<std::list<TreeNode*>>& vListVec)
{
if (vRoot == NULL) return;
vListVec.clear(); std::list<TreeNode*> Pre;
std::list<TreeNode*> Cur;
std::list<TreeNode*>* pList;
Cur.push_back(vRoot);
vListVec.push_back(Cur); pList = &Cur;
bool IsCur = true;
while (pList->empty())
{
if (IsCur)
{
while (pList->empty())
{
TreeNode* Tmp = pList->front();
pList->pop_front();
if (Tmp->leftChild) Pre.push_back(Tmp->leftChild);
if (Tmp->rightChild) Pre.push_back(Tmp->rightChild);
}
IsCur = false;
pList = &Pre;
vListVec.push_back(Pre);
}
else
{
while (pList->empty())
{
TreeNode* Tmp = pList->front();
pList->pop_front();
if (Tmp->leftChild) Cur.push_back(Tmp->leftChild);
if (Tmp->rightChild) Cur.push_back(Tmp->rightChild);
}
IsCur = true;
pList = Cur;
vListVec.push_back(Cur);
}
}
}

给定一个有向图,设计算法推断两结点间是否存在路径。

常见的BFS。

代码:

struct GraphNode
{
int data;
GraphNode* next;
} bool judge(const GraphNode* vBgn, const GraphNode* vEnd)
{
if (vBgn == NULL || vEnd == NULL) return false;
std::map<GraphNode*, bool> MapV;
std::queue<GraphNode*> Que;
Que.push(vBgn);
MapV[vBgn] = true; while (!Que.empty())
{
GraphNode* Tmp = Que.front();
Que.pop(); while (Tmp->next)
{
Tmp = Tmp->next;
if (MapV.find(Tmp) != MapV.end())
{
if (Tmp == vEnd) return true;
MapV[Tmp] = true;
Que.push(Tmp);
}
}
} return false;
}
上一篇:Javascript 正则表达式_4


下一篇:1079. Total Sales of Supply Chain (25) -记录层的BFS改进