首页 > 代码库 > (017)将一棵二叉查找树重构成链表(keep it up)

(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;
}






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