快捷導(dǎo)航

Java中關(guān)于二叉樹層序遍歷深入了解

更新時間：2021年09月17日 16:46:14 作者：bigsai

二叉樹的層序遍歷是面試經(jīng)常會被考察的知識點，甚至要求當(dāng)場寫出實現(xiàn)過程。層序遍歷所要解決的問題很好理解，就是按二叉樹從上到下，從左到右依次打印每個節(jié)點中存儲的數(shù)據(jù)，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

前言

大家好，我是bigsai，在數(shù)據(jù)結(jié)構(gòu)與算法中，二叉樹無論是考研、筆試都是非常高頻的考點內(nèi)容，在二叉樹中，二叉樹的遍歷又是非常重要的知識點，今天給大家講講二叉樹的層序遍歷。

這部分很多人可能會但是需要注重一下細節(jié)。

前面介紹了二叉排序樹的構(gòu)造和基本方法的實現(xiàn)，遍歷也是比較重要的一環(huán)，并且二叉樹的層序遍歷也是bfs的最簡單情況，這里我就將二叉樹的層序遍歷以及?？紗栴}給大家分享一下。

在了解二叉樹的遍歷之前，需要具備數(shù)據(jù)結(jié)構(gòu)與算法有隊列、遞歸、棧、二叉樹，這些內(nèi)容咱們前面都有講過，有這方面知識欠缺的同學(xué)可以往前翻一翻看一看！

層序遍歷

層序遍歷，聽名字也知道是按層遍歷。一個節(jié)點有左右節(jié)點，按層處理就是當(dāng)前層兄弟節(jié)點的優(yōu)先級要大于子節(jié)點處理的優(yōu)先級，所以就是要將子節(jié)點放到后面處理，這就適合隊列這個數(shù)據(jù)結(jié)構(gòu)用來存儲。

對于隊列，先進先出。從root節(jié)點push到隊列，那么隊列中先出來的順序是第二層的左右(假設(shè)都有)，第二層每個節(jié)點執(zhí)行的時候按照左右順序添加到隊列，第三層的節(jié)點就會有序的放到最后面……按照這樣的規(guī)則就能得到一個層序遍歷的順序。

實現(xiàn)的代碼也很容易理解：

public int[] levelOrder(TreeNode root) {
        int arr[]=new int[10000];
        int index=0;
        Queue<TreeNode>queue=new ArrayDeque<>();
        if(root!=null)
            queue.add(root);
        while (!queue.isEmpty()){
            TreeNode node=queue.poll();
            arr[index++]= node.val;
            if(node.left!=null)
                queue.add(node.left);
            if(node.right!=null)
                queue.add(node.right);
            
        }
        return Arrays.copyOf(arr,index);
    }

分層存儲

但是在具體筆試他可能要求你分層存儲，例如力扣的102二叉樹的層序遍歷，要求返回一個List<List<Integer>>類型。

這種相比上面一個多了一層邏輯就是每一層數(shù)據(jù)放到一塊，這個也很容易，最好想到的就是兩個隊列(容器)一層一層遍歷存儲，然后交替，但是兩個隊列(容器)的寫法常常會被面試官嫌棄，很多面試官讓你想想怎么不用兩個容器實現(xiàn)？

不用雙隊列去枚舉結(jié)果也很容易，重要的就是先記錄隊列大小size(當(dāng)前層節(jié)點數(shù)量)，然后執(zhí)行size次數(shù)的枚舉即可，具體代碼為：

public List<List<Integer>> levelOrder(TreeNode root) {
  List<List<Integer>>list=new ArrayList<List<Integer>>();
  if(root==null)return list;
  Queue<TreeNode>q1=new ArrayDeque<TreeNode>();
  q1.add(root);
  while (!q1.isEmpty()) {
    int size=q1.size();
    List<Integer>value=new ArrayList<Integer>();
    for(int i=0;i<size;i++)
    {
      TreeNode pNode=q1.poll();
      if(pNode.left!=null)
        q1.add(pNode.left);
      if(pNode.right!=null)
        q1.add(pNode.right);
      value.add(pNode.val);
    }
    list.add(value);
  }
  return list;
}

之字形打印

除了這個直接層序遍歷，二叉樹還有很高頻的就是之字形遍歷，例如劍指offer32和力扣103 二叉樹的鋸齒形層序遍歷，它的題目要求為：

請實現(xiàn)一個函數(shù)按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。

這道題雖然不是難題，但是有點繞，本來隊列這玩意我們就要大腦想一下什么順序，又出來一個之字形，屬實增加的思維邏輯，有不少小伙伴反映當(dāng)時面試官讓手撕這道題，自己以前明明寫過，但是太緊張自己給自己繞進去了！

其實這個問題也很容易轉(zhuǎn)化，因為值只是存儲，我們按照老樣子去進行層序遍歷，只不過在遍歷時候通過當(dāng)前層奇偶數(shù)來給它判斷是從左往右存儲到結(jié)果中還是從右往左放到結(jié)果中。當(dāng)然，判斷奇數(shù)偶數(shù)也很容易，可以用變量，也可以用結(jié)果List的size()都可。

個人實現(xiàn)的一個樸素代碼為：

public List<List<Integer>> levelOrder(TreeNode root) {
  List<List<Integer>> value=new ArrayList<>();//存儲到的最終結(jié)果
  if(root==null)
    return value;
  int index=0;//判斷
  Queue<TreeNode>queue=new ArrayDeque<>();
  queue.add(root);
  while (!queue.isEmpty()){
    List<Integer>va=new ArrayList<>();//臨時 用于存儲到value中
    int len=queue.size();//當(dāng)前層的數(shù)量
    for(int i=0;i<len;i++){
      TreeNode node=queue.poll();
      if(index%2==0)
        va.add(node.val);
      else
        va.add(0,node.val);
      if(node.left!=null)
        queue.add(node.left);
      if(node.right!=null)
        queue.add(node.right);
    }
    value.add(va);
    index++;
  }
  return value;
}

上面實現(xiàn)代碼也僅使用一個隊列，不過這個問題可能有很多更巧妙的解法需要大家自己去挖掘。