102.二叉樹(shù)的層序遍歷
廣度優(yōu)先搜索：
我們可以想到最樸素的方法是用一個(gè)二元組 (node, level) 來(lái)表示狀態(tài)，它表示某個(gè)節(jié)點(diǎn)和它所在的層數(shù)，每個(gè)新進(jìn)隊(duì)列的節(jié)點(diǎn)的 level 值都是父親節(jié)點(diǎn)的 level 值加一。最后根據(jù)每個(gè)點(diǎn)的 level 對(duì)點(diǎn)進(jìn)行分類，分類的時(shí)候我們可以利用哈希表，維護(hù)一個(gè)以 level 為鍵，對(duì)應(yīng)節(jié)點(diǎn)值組成的數(shù)組為值，廣度優(yōu)先搜索結(jié)束以后按鍵 level 從小到大取出所有值，組成答案返回即可。
考慮如何優(yōu)化空間開(kāi)銷：如何不用哈希映射，并且只用一個(gè)變量 node 表示狀態(tài)，實(shí)現(xiàn)這個(gè)功能呢？
我們可以用一種巧妙的方法修改廣度優(yōu)先搜索：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-729050.html
- 首先根節(jié)點(diǎn)入隊(duì)
- 當(dāng)隊(duì)列不為空時(shí)：
- 求當(dāng)前隊(duì)列的長(zhǎng)度 s i s_i si?
- 依次從隊(duì)列中取 s i s_i si?個(gè)元素進(jìn)行拓展，然后進(jìn)入下一次迭代
它和普通廣度優(yōu)先搜索的區(qū)別在于：普通廣度優(yōu)先搜索每次只取一個(gè)元素拓展，而這里每次取 s i s_i si?個(gè)元素文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-729050.html
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if(root == null){
return ans;
}
//隊(duì)列是先進(jìn)先出
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root); //隊(duì)列中添加根節(jié)點(diǎn)
while(!queue.isEmpty())
{
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for(int i = 1;i<=currentLevelSize;i++){
TreeNode node = queue.poll();
level.add(node.val);
//如果左節(jié)點(diǎn)不為空，隊(duì)列中先添加左節(jié)點(diǎn)
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
ans.add(level);
}
return ans;
}
}
到了這里，關(guān)于【LeetCode熱題100】--102.二叉樹(shù)的層序遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
