트리 순회 알고리즘 (Level Order Of Binary Tree)

트리 순회 알고리즘 (Level Order Of Binary Tree)

- 이진트리의 순회 방법으로 트리의 레벨 순으로 순회 한다.

- 한 레벨의 모든 노드를 방문 하고, 다음 레벨을 방문한다.

 

 

 

INPUT 작성

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int val) {
	    this.val = val;
	}
}

public class Example {

	public static void main(String[] args) {
		TreeNode root 		= new TreeNode(3);
		root.left		= new TreeNode(4);
		root.right		= new TreeNode(5);
		root.left.left		= new TreeNode(6);
		root.right.right	= new TreeNode(7);
		System.out.println(solve(root));
	}
}

 

 

OUTPUT 작성

public class Algo {
	
	public static List<List<Integer>> solve(TreeNode root) {
		List<List<Integer>> result	= new ArrayList<>();
		Queue<TreeNode> 	queue	= new LinkedList<TreeNode>();
		
		// 매개변수의 값이 존재하지 않다면, 탈출
		if (root == null) return result;
		
		// 최상단 노드의 값 초기화
		queue.offer(root);
		
		// 큐가 비어 있지 않다면
		while(!queue.isEmpty()) {
			int size = queue.size();	// 1 -> 2 -> 2
			
			List<Integer> list = new LinkedList<>();
			
			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); // 큐에 추가
			}
			
			// Answer 
			result.add(list);
		}
		return result;
	}
}