[PYTHON] Let Code Day7 starting from zero "104. Maximum Depth of Binary Tree"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Basically, I would like to solve the easy acceptance in descending order.

Last time Leet Code Day6 Starting from Zero "1342. Number of Steps to Reduce a Number to Zero"

It lasted for a week without skipping. Congratulations.

problem

104. Maximum Depth of Binary Tree

It's a fairly early problem, but I felt it was a good problem to understand the structure of the binary tree.

Given a binary tree, you will be asked to write an algorithm that finds the maximum value for that depth.

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

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

# 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:
        depth = 0
        stack = [(root,1)]
        
        while stack:
            root,length = stack.pop()
            if not root:
                return 0
            
            if length > depth:
                depth = length
            if root.right:
                stack.append((root.right,length + 1))
            if root.left:
                stack.append((root.left,length + 1))
        return depth
# Runtime: 40 ms, faster than 70.51% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 14.9 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.

Written in a depth-first search as described in the previous problem with binary search trees, Leet Code Day4 "938. Range Sum of BST" starting from zero Saw.

I found out by looking it up on Discuss etc., but there is also such a way of writing.

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

from collections import deque

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        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))
# Runtime: 36 ms, faster than 89.87% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 15 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.

It is implemented using deque.

Deque is a generalization of stacks and queues (the name is pronounced "deck", which is an abbreviation for "double-ended queue"). Deques can be append and pop from either side, are thread-safe and memory-efficient, and can run with approximately O (1) performance from either direction.

It's as fast as it sounds. Actually, the Runtime is also faster than other answers.