云淡風(fēng)輕近午天启涯，傍花隨柳過前川难述。
時(shí)人不識(shí)余心樂，將謂偷閑學(xué)少年红符。
程顥的《春日偶成》蔚龙，大概意思是忙里偷閑的感覺很爽(上班摸魚寫題感覺確實(shí)爽~)
二叉樹的層序遍歷
思路:queue
BFS的思想 (゜- ゜)つ,實(shí)在沒什么好解釋的冰评，過程省略~
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; ++i){
root = queue.poll();
list.add(root.val);
if(root.left != null){
queue.offer(root.left);
}
if(root.right != null){
queue.offer(root.right);
}
}
res.add(list);
}
return res;
}
}
時(shí)間復(fù)雜度:
二叉樹的每個(gè)節(jié)點(diǎn)進(jìn)出隊(duì)列各一次，所以時(shí)間復(fù)雜度為O(N)
額外空間復(fù)雜度:
額外使用了隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)木羹，隊(duì)列中元素的個(gè)數(shù)不會(huì)超過n個(gè)甲雅，額外空間復(fù)雜度為O(N)
執(zhí)行結(jié)果:
二叉樹的鋸齒形層次遍歷
思路：queue
較上一題而言，只需要加入奇偶的判斷即可坑填，實(shí)在沒什么好解釋的了抛人，具體可以見代碼
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean isLeftToRight = false;
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
isLeftToRight = !isLeftToRight;
for(int i = 0; i < size; ++i){
root = queue.poll();
if(isLeftToRight){
list.add(root.val);
}else{
list.add(0,root.val);
}
if(root.left != null){
queue.offer(root.left);
}
if(root.right != null){
queue.offer(root.right);
}
}
res.add(list);
}
return res;
}
時(shí)間復(fù)雜度：O(N)
額外空間復(fù)雜度：O(N)
執(zhí)行結(jié)果：
