[leetcode] 104. Maximum Depth of Binary Tree

원문)

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path
from the root node down to the farthest leaf node.

번역)

이진트리가 주어졌을때, 최대 depth를 구하라.
최대 depth는 루트로드로부터 가장 먼곳에 있는 리프노드 까지의 경로를
추적한 노드의 숫자이다.


예제)

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

문제접근)
여러번 계속 recursive와 while문으로 풀어버릇하면 감이 오는것 같다.

코드)

1. top-down

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

# 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: return self.top_down(root, 0) def top_down(self, root: TreeNode, depth: int): if root is None: return depth l_m = self.top_down(root.left, depth+1) r_m = self.top_down(root.right, depth+1) return max(l_m, r_m)

2. bottom-up

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

# 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: stack = [(root, 1)] depth = 0 while stack: cur, lv = stack.pop() if cur: stack.append((cur.left, lv + 1)) stack.append((cur.right, lv + 1)) depth = max(depth, lv) return depth