算法Day12-層次遍歷二叉樹

2019-11-11 06:08:58

字體：大中小

供稿：網(wǎng)友

題目

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

解析

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

代碼

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

上一篇：xgboost介紹

下一篇：CODE[VS] 天梯 1204 尋找子串位置