今天全部是層序遍歷蟀架！
- 102.二叉樹的層序遍歷
- 107.二叉樹的層次遍歷II
- 199.二叉樹的右視圖
- 637.二叉樹的層平均值
- 429.N叉樹的層序遍歷
- 515.在每個(gè)樹行中找最大值
- 116.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針
- 117.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針I(yè)I
-
102.二叉樹的層序遍歷
我愿稱之為最初的經(jīng)典。兩天前的文章已經(jīng)詳細(xì)分析過榆骚，在此就不再分析片拍。在此處粘貼出本題的代碼意在展示層序遍歷的基本結(jié)構(gòu)，后面的題目都是在此結(jié)構(gòu)的基礎(chǔ)上進(jìn)行修改妓肢，因此可對(duì)照查看從而牢記此結(jié)構(gòu)捌省。
class Solution {
public List<List<Integer>> resultList = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
checkFun02(root);
return resultList;
}
public void checkFun02(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
int levelSize = queue.size();
while(levelSize > 0){
TreeNode tempNode = queue.poll();
list.add(tempNode.val);
if(tempNode.left != null) queue.offer(tempNode.left);
if(tempNode.right != null) queue.offer(tempNode.right);
levelSize--;
}
resultList.add(list);
}
}
}
這是基礎(chǔ)代碼框架，后續(xù)題目的代碼都是在此基礎(chǔ)上進(jìn)行修改得到的碉钠，我會(huì)在后續(xù)代碼中以注釋的方式來注明 后續(xù)題目中 根據(jù)題目的要求 需要在此框架的基礎(chǔ)上作出修改的地方纲缓。
-
107.二叉樹的層次遍歷II
本題是在層序遍歷的基礎(chǔ)上，要求輸出的順序是自底向上喊废。那其實(shí)就是在基礎(chǔ)的層序遍歷基礎(chǔ)上祝高，每層遍歷完之后的結(jié)果加入到List鏈表的頭節(jié)點(diǎn)處。完整代碼如下：
class Solution { //Java
public List<List<Integer>> result = new LinkedList<>();
public List<List<Integer>> levelOrderBottom(TreeNode root) {
checkFun03(root);
return result;
}
public void checkFun03(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
List<Integer> curLevel = new ArrayList<>();
for(int i = 0; i < levelSize; i++){
TreeNode curNode = queue.poll();
curLevel.add(curNode.val);
if(curNode.left != null){
queue.add(curNode.left);
}
if(curNode.right != null){
queue.add(curNode.right);
}
}
result.add(0,curLevel); // Add the node of the current layer to the head of the linked list
}
}
}
-
199.二叉樹的右視圖
本題是要輸出每一層的最右側(cè)的元素污筷。那就是在每層遍歷到最后一個(gè)元素時(shí)工闺，把該元素的值加入到結(jié)果集result中就好。
class Solution { // Java
List<Integer> result = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
findMostRightList(root);
return result;
}
public void findMostRightList(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
TreeNode rightMostNode = null;
while(levelSize > 0){
TreeNode currentNode = queue.poll();
rightMostNode = currentNode; // to locate the most right Node
if(currentNode.left != null) queue.add(currentNode.left);
if(currentNode.right != null) queue.add(currentNode.right);
levelSize--;
}
if(rightMostNode != null){
result.add(rightMostNode.val); // add the value to result
}
}
}
}
可以看到瓣蛀，我們是定義了一個(gè)叫做rightMostNode的變量/指針來記錄每層的最右邊的元素斤寂，邏輯是隨著內(nèi)層while循環(huán)的進(jìn)行，rightMostNode會(huì)逐漸指向右邊的元素揪惦，當(dāng)內(nèi)側(cè)while循環(huán)結(jié)束時(shí)遍搞，rightMostNode所指向的就是最右邊的元素，然后我們執(zhí)行result.add()器腋，就把值加入到集合中了溪猿。
-
637.二叉樹的層平均值
本題是在層序遍歷的過程中，記錄每一層的節(jié)點(diǎn) 值的平均值纫塌，因此就需要求和诊县，然后同時(shí)每層的元素個(gè)數(shù)levelSize也要記錄，才方便后續(xù)求出平均值措左。完整代碼如下：
class Solution { // Java
List<Double> result = new ArrayList<>();
public List<Double> averageOfLevels(TreeNode root) {
findAvg(root);
return result;
}
public void findAvg(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
Double levelSum = 0.0; // record the sum in a level
int levelNum = levelSize; // record the levelSize
while(levelSize > 0){ // for循環(huán)替代的是這個(gè)while循環(huán)
TreeNode cur = queue.poll();
levelSum += cur.val; // get sum
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
levelSize--;
}
Double avg = levelSum / levelNum; // get the average
result.add(avg) ;
}
}
}
代碼的注釋很清晰的記錄了在基礎(chǔ)結(jié)構(gòu)上所做出的改動(dòng)依痊。其中值得說明的是，內(nèi)層while循環(huán)可以被for循環(huán)完美替代，每一個(gè)層序遍歷都是如此胸嘁，而在本題中瓶摆，使用for循環(huán)替代的好處是 可以不用定義一個(gè)levelNum來記錄levelSize了，因?yàn)槿绻褂脀hile循環(huán)的話性宏，levelSize就變成了循環(huán)控制因素群井，就會(huì)變化；而使用for循環(huán)毫胜，levelSize就不會(huì)變书斜。
for (int i = 0; i < levelSize; i++) { // 替代上述while循環(huán)的for循環(huán)代碼
TreeNode cur = queue.poll();
levelSum += cur.val;
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
-
429.N叉樹的層序遍歷
這題就是把二叉樹換成了N叉樹，所以就是在遍歷每個(gè)節(jié)點(diǎn)的后面酵使，要把下一層節(jié)點(diǎn)加入到隊(duì)列中時(shí)荐吉，把左子樹、右子樹 這部分的代碼 替換成 一個(gè)for循環(huán)口渔，循環(huán)遍歷N叉樹節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)組样屠，然后把每個(gè)子節(jié)點(diǎn)都加入到隊(duì)列。
class Solution { // Java
public List<List<Integer>> result = new LinkedList<>();
public List<List<Integer>> levelOrder(Node root) {
findLevelOrder(root);
return result;
}
public void findLevelOrder(Node root){
if(root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
List<Integer> levelList = new ArrayList<>();
while(levelSize > 0){
Node tempNode = queue.poll();
levelList.add(tempNode.val);
for(Node n : tempNode.children){ // add all children of Node to the queue
if(n != null) queue.add(n);
}
levelSize--;
}
result.add(levelList);
}
}
}
-
515.在每個(gè)樹行中找最大值
本題也比較好想搓劫，遍歷每層時(shí)瞧哟，加入一個(gè)變量一直記錄當(dāng)前層的最大值，當(dāng)一層遍歷結(jié)束時(shí)枪向，把最大值加入到結(jié)果集result中勤揩。完整代碼如下：
class Solution {
public List<Integer> result = new ArrayList<>();
public List<Integer> largestValues(TreeNode root) {
findLargestValue(root);
return result;
}
public void findLargestValue(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
int largestNum = Integer.MIN_VALUE;
while(levelSize > 0){
TreeNode tempNode = queue.poll();
largestNum = Math.max(largestNum, tempNode.val); // record the largest number
if(tempNode.left != null) queue.offer(tempNode.left);
if(tempNode.right != null) queue.offer(tempNode.right);
levelSize--;
}
result.add(largestNum);
}
}
}
-
116.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針
本題就是在處理每個(gè)節(jié)點(diǎn)時(shí)，把它的next指針指向右側(cè)的節(jié)點(diǎn)秘蛔。對(duì)此我們采用的一個(gè)較為巧妙的做法是把彈出的當(dāng)前節(jié)點(diǎn)指向隊(duì)列queue中的頂部節(jié)點(diǎn)queue.peek();這是因?yàn)槲覀兊脑厥前凑諒淖蟮接抑饾u加入的陨亡，所以正好 對(duì)于當(dāng)前彈出的元素tempNode而言，他要指向的元素深员，也就是在二叉樹中位于他同層右邊一位的元素负蠕，就正好在隊(duì)列頂部。另外需要說明的一點(diǎn)是倦畅，本題有個(gè)特殊處理遮糖，那就是每層最右邊的元素沒人可指，但好在他原本的next值就是null叠赐，因此不需要額外處理欲账，只需處理前面 levelSize-1 個(gè)元素的next指針就好。
class Solution { //Java
public Node connect(Node root) {
connectNode(root);
return root;
}
public void connectNode(Node root){
if(root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
for(int i = 0; i < levelSize; i++){
Node tempNode = queue.poll();
if(i < levelSize - 1){ // 處理前l(fā)evelSize-1個(gè)元素就好
tempNode.next = queue.peek(); // 隊(duì)列頂端元素正好是下一個(gè)元素
}
if(tempNode.left != null) queue.offer(tempNode.left);
if(tempNode.right != null) queue.offer(tempNode.right);
}
}
}
}
-
117.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針I(yè)I
本題與上一題LeetCode編號(hào)116的基本一樣赛不，唯一區(qū)別就在于116題中給出的二叉樹為完美二叉樹，而117題（本題）是普通二叉樹殿较。但在層序遍歷的代碼上是一樣的抓艳，這是因?yàn)槲覀儼言丶尤氲疥?duì)列中時(shí)，就是按照每層的順序添加的，因此空位的地方自動(dòng)就被忽略了对供，所以代碼不需要修改即可直接使用氛濒。
總結(jié)
層序遍歷最重要的還是框架【┚埃框架主體結(jié)構(gòu)如下：
首先就是定義一個(gè)全局變量result來收集結(jié)果（大部分都需要收集結(jié)果，然后根據(jù)題目的要求可能是List<>鄙皇，也可能是List<List<>>.
然后就是定義一個(gè)方法來解決主要邏輯：
因?yàn)橛辛巳肿兞縼硎占Y(jié)果，所以一般參數(shù)只需傳入根節(jié)點(diǎn)root就好。
方法內(nèi)先判斷是否為空 if(root == null) return;
然后創(chuàng)建隊(duì)列Queue<TreeNode> queue = new LinkedList<>(); 隊(duì)列不能用ArrayList漱竖。
緊接著把root放入隊(duì)列中 queue.add(root); 此處用queue.offer(root);也行
然后是外層while循環(huán) while(!queue.isEmpty()){ 循環(huán)體1 }
在循環(huán)體1中 首先要做的就是記錄每層的大小levelSize，即當(dāng)前層有幾個(gè)節(jié)點(diǎn)悼吱。
然后根據(jù)需要可以創(chuàng)建一個(gè)數(shù)組/鏈表來收集本層信息。
所以 外層循環(huán)里所做事情的含義就是 對(duì)于每一層都要用到的信息可以提取到這里遇西。例如levelSize就是用來記錄每層的節(jié)點(diǎn)個(gè)數(shù)，List<Integer>就是用來記錄每層的節(jié)點(diǎn)的值茄蚯。
內(nèi)層循環(huán)。
內(nèi)層循環(huán)可以是while循環(huán)皱碘，用levelSize > 0來控制尸执，但是每次循環(huán)后得levelSize-1。因此levelSize的值會(huì)隨著循環(huán)的進(jìn)行而變化褪贵。
內(nèi)層循環(huán)也可以是for循環(huán)，用for(int i = 0, i < levelSize; i++){}來控制。好處就是levelSize不變歼培。具體使用看本文前半部分第四題查剖。
內(nèi)層循環(huán)的內(nèi)部邏輯則是需要根據(jù)題意來了，但大體框架是先做邏輯（例如把節(jié)點(diǎn)的值添加到集合中直砂，又或者是求得節(jié)點(diǎn)的值之和...）掘托；然后添加元素，對(duì)于二叉樹基本都是
if(tempNode.left != null) queue.add(tempNode.left);
if(tempNode.right != null) queue.add(tempNode.right); 這兩句。
稍微特殊點(diǎn)的就是那個(gè)N叉樹椅挣，但是原理也是一樣，都是遍歷所有的子節(jié)點(diǎn)然后添加。
最后就是在內(nèi)層循環(huán)結(jié)束后，但是外層循環(huán)結(jié)束前肌似。
在這里的話就是 如果需要把當(dāng)前層的結(jié)果作為一個(gè)集合收集起來受楼，就需要用全局變量result來收集它对雪。result.add(List);
