LeetCode. Maximum Depth of Binary Tree [Trees]

Problem:

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.

Note: A leaf is a node with no children.

Example:

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

 

return its depth = 3.

 

-Summary-

Solve recursively

1. Find the maximum length of depth by comparing the left and right subtree.

2. Add 1 for the root depth and return.

 

사람들이 푼 것을 보니 recursive 하게 말고도 BFS 알고리즘으로 푸는 방법이 있었다.

 

leetcode.com/problems/maximum-depth-of-binary-tree/discuss/34434/Python-solution-(BFS-+-dequequeue)

# BFS + deque   
def maxDepth(self, root):
    if not root:
        return 0
    from collections import deque
    queue = deque([(root, 1)])
    while queue:
        curr, val = queue.popleft()
        if not curr.left and not curr.right and not queue:
            return val
        if curr.left:
            queue.append((curr.left, val+1))
        if curr.right:
            queue.append((curr.right, val+1))

혹시라도 파이썬의 self 문법이 이해가 안된다면 아래 글을 참조.

https://pythontips.com/2013/08/07/the-self-variable-in-python-explained/

The self variable in python explained

https://www.programiz.com/article/python-self-why

self in Python, Demystified

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]