Binary Tree Level Order Traversal (leetcode 102/103/107)
文章目录
Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
BFS
思路: 典型的BFS, 使用queue. 两层循环,外层判断queue 是否为空,内层for循环queue的size,然后逐个弹出node, 把左右儿子再压入。 注意开始的root == null 的判断。
时间复杂度: O(N)
空间复杂度: O(w) where w is maximum width of Binary Tree.
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if (root == null) {
return result;
}
queue.add(root);
while (queue.peek() != null) {
int size = queue.size();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
result.add(list);
}
return result;
}
}
Binary Tree Level Order Traversal 2
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
思路: BFS, 因为是bottom-up, 所以每次加入list都加到开头:bfs.add(0, level);
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> bfs = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if (root == null) {
return bfs;
}
queue.add(root);
while(!queue.isEmpty()){
ArrayList<Integer> level = new ArrayList<Integer>();
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode head = queue.poll();
level.add(head.val);
if(head.left != null){
queue.add(head.left);
}
if(head.right != null){
queue.add(head.right);
}
}
bfs.add(0, level);
}
return bfs;
}
}
Binary Tree Zigzag Level Order Traversal
思路: 设置一个flag,来确定该层是从左往右,还是从右往左。Collections.reverse(level) 变换方向。
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(root == null){
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int flag = -1;
while(queue.peek() != null){
flag = 0 - flag;
int size = queue.size();
List<Integer> level = new ArrayList<Integer>();
for(int i = 0; i < size; i++){
TreeNode head = queue.poll();
level.add(head.val);
if(head.left != null){
queue.offer(head.left);
}
if(head.right != null){
queue.offer(head.right);
}
}
if(flag == -1){
Collections.reverse(level);
}
result.add(level);
}
return result;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论