Maximum Depth of Binary Tree_BFS

BFS, Queue

Data Structure : Queue

Algorithm 1. 노드 타입의 큐 생성. 2. 큐가 비어있을 때까지 Poll, Offer 반복한다.( Poll 하는 동시에 Offer) 3. 각 레벨마다 깊이를 +1씩 증가시킨다.

Technique & skill 1. 반복문의 위치와 구조. 논리적으로 생각하기!

Implement Algorithms in 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 {//BFS, Queue
    public int maxDepth(TreeNode root) {
        //1.자료구조 생성
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        
        //2. 반복문 돌린다.
        //큐가 빌 때까지 offer와 poll을 반복한다.
        while(!queue.isEmpty()) {
            int size = queue.size();
            
            //큐 갯수만큼 poll하고 나서 깊이 +1 증가시킨다.
            for(int i=0;i<size;i++) {//큐의 갯수만큼 poll한다.
                TreeNode node = queue.poll();//poll하면서 동시에 왼쪽 자식 오른쪽 자식 넣는다!
                if(node.left != null) {queue.offer(node.left);}
                if(node.right != null) {queue.offer(node.right);}
            }
            depth++;//0->1->2->3
        }
        return depth;
    }
}