[알고리즘] leetcode - 104번

문제

• 문제
  이진 트리의 루트 노드가 주어졌을 때, 이 트리의 최대 깊이를 구하세요.

트리의 깊이는 루트 노드에서 가장 먼 리프 노드까지의 경로에 포함된 노드의 수를 의미합니다.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode([this.val = 0, this.left, this.right]);
 * }
 */
class Solution {
  int maxDepth(TreeNode? root) {
  }
}

• 조건

1. 트리는 비어있지 않으며, 노드의 개수는 0에서 10,000 사이입니다.

• 예시
  예시1.
  입력: [3,9,20,null,null,15,7]
  트리 구조:

  3

  / \
  9 20
  / \
  15 7

  출력: 3
  설명: 루트 노드 3에서 리프 노드 15 또는 7까지의 경로 길이는 3입니다.

예시2.
입력: [1, null, 2]
트리 구조:

1
\
2

출력: 2
설명: 루트 노드 1에서 리프 노드 2까지의 경로 길이는 2입니다.

풀이 결과

해결

막혔던점 혹은 이유

재귀함수를 오랜만에 보게되어 햇갈렸었다.

배운점

.

런타임 가장빠른 답

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode([this.val = 0, this.left, this.right]);
 * }
 */
class Solution {
  int maxDepth(TreeNode? root) {
    if (root == null) return 0;
    int rightDepth = maxDepth(root.right);
    int leftDepth = maxDepth(root.left);
    return rightDepth > leftDepth ? rightDepth + 1 : leftDepth + 1;
  }
}

메모리 가장 적은 답

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode([this.val = 0, this.left, this.right]);
 * }
 */
class Solution {
  int maxDepth(TreeNode? root) {
    if (root == null) return 0;


    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);

    return max(rightDepth,leftDepth)+1;
  }
}