Maximum Depth of Binary Tree

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

Maximum Depth of Binary Tree - LeetCode

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

문제

tree가 들어왔을 때 깊이를 출력하는 문제입니다.

 

실행코드

from collections import deque

def maxDepth(root):
  max_depth = 0
  if root is None:
    return 0

  q = deque()
  q.append((root, 1))
  while q:
    cur_node, cur_depth = q.popleft()
    max_depth = max(max_depth, cur_depth)
    if cur_node.left:
      q.append((cur_node.left, cur_depth + 1))
    if cur_node.right:
      q.append((cur_node.right, cur_depth + 1))
      
  return max_depth

root = [3, 9, 20, None, None, 15, 7]

class TreeNode:
  def __init__(self, l = None, r = None, v = 0):
    self.left = l
    self.right = r
    self.value = v

root = TreeNode( v = 3)
root.left = TreeNode(v = 9)
root.right = TreeNode(v = 20)
root.right.left = TreeNode(v = 15)
root.right.right = TreeNode(v = 7)


print(maxDepth(root))

TreeNode로 input일때 tree를 구현해 주었습니다.

MaxDepth함수는 bfs 순회를 사용하여 tree의 깊이를 주해주었습니다.

 

DFS사용

def maxDepth(root):
  if root is None:
    return 0
  left_depth = maxDepth(root.left)
  right_depth = maxDepth(root.right)
  return max(left_depth, right_depth) + 1


root = [3, 9, 20, None, None, 15, 7]

class TreeNode:
  def __init__(self, l = None, r = None, v = 0):
    self.left = l
    self.right = r
    self.value = v

root = TreeNode( v = 3)
root.left = TreeNode(v = 9)
root.right = TreeNode(v = 20)
root.right.left = TreeNode(v = 15)
root.right.right = TreeNode(v = 7)


print(maxDepth(root))

DFS를 사용하여 코드를 더욱 효율적으로 변화시켰습니다.