Binary Tree Level Order Traversal
Level Order Of Binary Tree
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).

Input : 3 / \ 4 5 /\ 6 7 Output : [[3], [4,5],[6,7]]
์๋ฃ๊ตฌ์กฐ : Queue(FIFO) - BFS(๋๋น์ฐ์ ), Stack(FILO) - DFS(๊น์ด์ฐ์ )
์๊ณ ๋ฆฌ์ฆ 0. ํ์ ์ฌ์ด์ฆ ์ฒดํฌ!, ๋ฆฌ์คํธ ์์ฑ! - level๋ณ๋ก ๋บ๊ฒ์ด๊ธฐ ๋๋ฌธ์ level ๋ณ๋ก ๋ฆฌ์คํธ ์์ฑํ๋ค.(ํ์์ ๋นผ๋ด๋ ๋ฐ๋ณต๋ฌธ ๋ค์ด๊ฐ๊ธฐ ์ ์ ๋ฆฌ์คํธ๋ฅผ ์์ฑํ๋ค.) 1. ํ์ ๋ ธ๋ ๋ฃ๋๋ค. 2. ๋ ธ๋ ๋นผ๋ฉด์ ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ์ ๋ ธ๋๊ฐ ์๋์ง ํ์ธํ๋ค. - ์ผ/์ค ์์๋ ๋ฌธ์ ์์ ์ ์. ๋ ธ๋ ๋นผ๋ฉด์ ๋ฌธ์ ์์ ์ ์๋ ์์(์ฌ๊ธฐ์๋ ์ผ->์ค)๋ก ๋ ธ๋ ๋ค์ ๋ฃ๋๋ค.
์๊ณ ๋ฆฌ์ฆ์ Java๋ก ๊ตฌํ
/**
* 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) {
//left->right : BFS, BFS = Queue!
List<List<Integer>> result = new ArrayList<>();
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++) {
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null) {queue.offer(node.left);}
if(node.right != null) {queue.offer(node.right);}
}
result.add(list);
}
return result;
}
}
Last updated
Was this helpful?