Chloe Jungah Kim
Chloe Jungah Kim
A blogger who writes about everything.

[Leetcode] 104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/
[Leetcode] 104. Maximum Depth of Binary Tree

binary tree가 주어졌을 때, 해당 트리의 최대 depth를 구하는 문제

  • depth는 root 노드에서부터 leaf 노드까지의 길이를 의미한다.
  • leaf 노드란 자식이 없는 노드를 의미한다.

Example 1

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

Example 2

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

Solution 1

Note

stack을 사용하여 depth first search 방식으로 트리 탐색

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root :
            return 0
        stack = [[root, 1]]
        res = 0
        while stack :
            temp = stack.pop()
            node = temp[0]
            if not node.right and not node.left :
                res = max(res, temp[1])
            if node.right :
                stack.append([node.right, temp[1] + 1])
            if node.left :
                stack.append([node.left, temp[1] + 1])
        return res

Solution 2

Note

  • recursive하게 해결
  • 한 단계씩 들어갈 때마다 depth 값을 1씩 증가시키는 방식
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        depth = 0
        if root.left:
            depth = self.maxDepth(root.left)
        if root.right:
            depth = max(depth, self.maxDepth(root.right))
        return depth+1
«
»