Maximum Depth of Binary Tree

📌 문제

• 트리의 최대 깊이를 구하는 문제

https://leetcode.com/problems/maximum-depth-of-binary-tree/

📌 문제 풀이 - DFS, BFS

DFS

bfs

📌 코드 - DFS

public class MainDFS {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(3);
        node.left = new TreeNode(9);
        node.right = new TreeNode(20);
        node.right.left = new TreeNode(15);
        node.right.right = new TreeNode(7);

        Solution solution = new Solution();
        solution.maxDepth(node);
    }
      public static 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;
          }
      }

    static class Solution {
        public int maxDepth(TreeNode root) {
            if(root == null) return 0;
            return dfs(root, 1);
        }

        private int dfs(TreeNode root, int cnt) {
            if(root.left == null && root.right==null ){
                return cnt;
            }
            int left=0;
            int right=0;
            if(root.left !=null) {
                left = dfs(root.left, cnt + 1);
            }
            if(root.right !=null) {
                right = dfs(root.right, cnt + 1);
            }
            return Math.max(left,right);
        }
    }
}

📌 코드 - BFS

import java.util.LinkedList;
import java.util.Queue;

public class MainBFS {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(3);
        node.left = new TreeNode(9);
        node.right = new TreeNode(20);
        node.right.left = new TreeNode(15);
        node.right.right = new TreeNode(7);

        Solution solution = new Solution();
        int i = solution.maxDepth(node);
        System.out.println(i);
    }
      public static 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;
          }

          @Override
          public String toString() {
              return "TreeNode{" +
                      "val=" + val +
                      ", left=" + left +
                      ", right=" + right +
                      '}';
          }
      }

    static class Solution {
        public int maxDepth(TreeNode root) {
            if(root == null) return 0;

            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int cnt = 0;

            while(!queue.isEmpty()){
                int level = queue.size();
                while( level -- > 0){
                    // poll 의 위치가 헷갈렸다.
                    TreeNode poll = queue.poll();
                    if(poll.left != null){
                        queue.offer(poll.left);
                    }
                    if(poll.right != null){
                        queue.offer(poll.right);
                    }
                }
                cnt++;
            }
            return cnt;
        }

    }
}