首页 > 代码库 > (017)将一棵二叉查找树重构成链表(keep it up)
(017)将一棵二叉查找树重构成链表(keep it up)
给定一棵二叉查找树,设计算法,将每一层的所有结点构建为一个
链表(也就是说, 如果树有D层,那么你将构建出D个链表).
这个题实质是个BFS,但是实现起来有点麻烦,又不像常见的BFS,
所以编写代码时有点艰难。
下面的代码使用两个list来实现层次遍历的,首先用Cur链表存储当前层
的结点,然后用Pre链表存储当前层的子层结点,Cur和Pre。下一次遍历时
链表(也就是说, 如果树有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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。