[LeetCode | Java | DFS/BFS 문제 풀이] 104. Maximum Depth of Binary Tree - Solution with DFS

99클럽 | 비기너

🎄 104. Maximum Depth of Binary Tree

🏷 Topic : Tree Binary Tree DFS; Depth-First Search

Easy

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

Accepted    3.1M  |  Submissions    4.1M  |  Acceptance Rate    75.5%

---

✔ Solution with DFS

/**
 * 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 int maxDepth(TreeNode root) {
        int depth = 0;

        if (root != null) {

            if (root.right != null) {
                depth = maxDepth(root.right);
            }
            if (root.left != null) {
                int depth2 = maxDepth(root.left);

                if (depth2 > depth) {
                    depth = depth2;
                }
            }

            return depth + 1;
        }

        return 0;

    }
}

채점 결과

💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍

LeetCode 업로드한 풀이 링크🔗

• 이진 트리의 Depth : 루트 노드에서 가장 먼 리프 노드까지
  가장 긴 경로를 따라 있는 노드 수
• int maxDepth(TreeNode root) : 매개변수로 TreeNode root를 받아서
  해당 노드에 대한 이진트리의 Depth를 반환하는 메서드

maxDepth()를 구현하여 이진트리의 최대 깊이를 반환하자.

1. 이진트리의 Depth를 할당할 int depth 변수 초기화

  int depth = 0;

2. 매개변수로 받은 TreeNode root가 null이 아니면 DFS 실행

• root의 right노드 탐색
  : root.right가 null이 아니면,
  depth에 right노드를 루트노드로 갖는 서브트리의 Depth를 할당
• depth = maxDepth(root.right);
• root의 left노드 탐색
  : root.left가 null이 아니면,
  int depth2를 left노드를 루트노드로 갖는 서브트리의 Depth로 초기화
• int depth2 = maxDepth(root.left);
• depth와 depth2를 비교하여
  depth2가 depth보다 크면 depth에 depth2를 할당
• if (depth2 > depth) { depth = depth2; }
• DFS를 끝내고 depth에 1 추가하여 반환
• return depth + 1;

3. root가 null이면 0을 반환

return 0;

4. 제약사항에서 이진 트리의 노드 수의 범위는 [0, 104]이므로
노드 수가 0개이면 Depth가 0

💬 무엇을 새롭게 알았는지

Depth of Binary Tree를 DFS로 구하는 방법을 알게되었다.

---

📚 References(참고 자료)

[Java 봐 | 자료 구조] 트리(Tree) 개념 정리

 

---

🆙 NEXT LEVEL

• 미들러: Reverse Odd Levels of Binary Tree
• 챌린저: 네트워크