算法Day12-層次遍歷二叉樹

2019-11-11 07:21:08

字體：大中小

供稿：網(wǎng)友

題目

給定一個二叉樹，返回其節(jié)點值的層次遍歷（即從左到右，一層一層遍歷）例如：給定二叉樹{3,9,20,#,#,15,7} 3 / / 9 20 / / 15 7 返回層次遍歷如下： [ [3], [9,20] [15,7] ]

解析

通過廣度優(yōu)先遍歷來實現(xiàn)層次遍歷。創(chuàng)建一個Queue來緩存每一層的樹節(jié)點，在遍歷Queue的過程中，每取出一個元素，將該元素的左右子節(jié)點按順序插入到Queue中。一直遍歷下去，直到Queue為空。

代碼

vector< vector<int> >levelOrder(TreeNode *root){ vector< vector<int> > result; if(root == NULL) return result; queue<TreeNode*> nodeQ; //先進(jìn)先出(FIFO) 隊列類型的nodeQ變量用來緩存每一層的數(shù)節(jié)點 nodeQ.push(root); //push int nextLevelCnt=0, currentLeveCnt=1; vector<int> layer; //layer存放的為某一層的節(jié)點數(shù)值，通過layer作為中間變量加入到result int visitedCnt=0; //訪問過的節(jié)點數(shù)目 while(nodeQ.size() != 0) // 隊列不為空時訪問，否則返回結(jié)果 { TreeNode* node = nodeQ.front(); nodeQ.pop(); visitedCnt++; layer.push_back(node->val); if(node->left != NULL) //為空時不做處理 { //不為空則進(jìn)隊列 nodeQ.push(node->left); nextLevelCnt++; } if(node->right != NULL) { nodeQ.push(node->right); nextLevelCnt++; } if(visitedCnt == currentLeveCnt) //訪問過的節(jié)點等于該層節(jié)點數(shù)時，開始下一層的訪問。 { //下一層訪問開始，visitedCnt置0，當(dāng)前層數(shù)節(jié)點數(shù)為上層的nextLevelCnt數(shù)，nextLevelCnt置0 visitedCnt = 0; currentLeveCnt = nextLevelCnt; nextLevelCnt = 0; result.push_back(layer); //將上層的節(jié)點加入結(jié)果 layer.clear(); } } return result;}

上一篇：[BZOJ2502]清理雪道（有源匯有上下界的最小流）

下一篇：mysql 2003以及10061錯誤