廣度優先搜索(BFS)的基本思想：

在二叉樹上進行BFS遍歷(對上圖解釋的代碼實現)

//BFS 使用隊列void bfs (TreeNode root){ Queuequeue=new ArrayDeque<>(); queue.add(root); while(!queue.isEmpty()){ TreeNode node=queue.poll();//隊頭元素出隊 //這個隊頭元數出隊完成后，對其左右子節點進行入隊 if(node.left!=null){queue.add(node.left);} if(node.right!=null){queue.add(node.right);} }}

廣度優先思想在本題上的應用

BFS 遍歷的結果集是一個一維數組，這題(層序遍歷)期望的結果是一個二維數組。因此許需要對BFS遍歷的結果集進行分層。

在BFS對二叉樹進行遍歷的時候，數組中會有不同層元素同時存在的情況，且這種情況下，無法區分哪些元素是來自哪一層。如下圖：

因此可以在每一層遍歷開始前，先記錄隊列中的結點數量(也就是這一層的結點數量)，然后一口氣處理完這一層的n個結點。

下面給出實現代碼：

void bfs(TreeNode root){ Queuequeue=new ArrayLise(); queue.add(root); while(!queue.isEmpty()){ int n=queue.size(); for(int i=0;i //變量i無實際意義，只是為了循環 TreeNode node=queue.poll();//隊頭元素出隊 //這個隊頭元數出隊完成后，對其左右子節點進行入隊 if(node.left!=null){queue.add(node.left);} if(node.right!=null){queue.add(node.right);} } }}

對上面的代碼進行適當的修改就可以得出本題的代碼：

class Solution { //外部list的元素個數就是樹的層數 //里面list的元素的個數就是樹的每層元素個數 public List> levelOrder(TreeNode root) { List> levels = new ArrayList>(); Queue queue=new ArrayDeque(); if(root!=null) queue.add(root); while(!queue.isEmpty()){ List level=new ArrayList(); int size= queue.size(); for(int i=0;i TreeNode node=queue.poll(); level.add(node.val);????????????????if(node.left!=null)?queue.add(node.left);????????????????if(node.right!=null)?queue.add(node.right); } levels.add(level); }????????return?levels;????????}

參考文章：https://mp.weixin.qq.com/s?__biz=MzA5ODk3ODA4OQ==&mid=2648167212&idx=1&sn=6af5ffe5b69075b21bb4743ddcee4e7c&chksm=88aa236abfddaa7cae70b42edb299d0a52d9f1cc4fc1fdba1116972fc0ca0275b8bfdf10851b&token=1607921395&lang=zh_CN#rd

下面再給出一個遞歸解法：

//遞歸解法Class Solution{ List<List> levels=new ArrayList<List>(); public void helper(TreeNode node,int level){ //在這種情況下要新建一個內部list用來存儲新的一層元素 if(levels.size()==level){ levels.add(new ArrayList())； } //新建完一層之后，把剛才傳入的結點添加到這個新建的內部list levels.get(level).add(node.val); //這個結點處理完成之后，處理這個結點的左子結點 //由于左子結點位于這個結點的下一層，所以層數要加一 if(node.left!=null) helper(node.left,level+1); //處理完成這個結點的左子結點后，處理右子結點 if(node.right!=null) helper(node.left,level+1); } public List<List> levelOrder(TreeNode root){ if(root==null) return levlels; helper(root,0) return levels } }

總結

以上是生活随笔為你收集整理的二叉树外部节点_leetcode 102 二叉树的层序遍历1 /BFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。