算法Day12-層次遍歷二叉樹

2019-11-14 08:51:13

字體：大中小

來源：轉載

供稿：網友

題目

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

解析

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

代碼

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

上一篇：Servlet學習 ——Web部分第十天

下一篇：588A. Duff and Meat