104. Maximum Depth of Binary Tree

Description:

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

We are trying to get a depth of binary tree.

In example 1, weshould return "3", and example 2 should return "2." 

Solution1(Recursion):

Recursive method

This is the method using recursive. We are going down to tree, adding 1 until the depth of tree.

Since the recursive function have both value l and r, we should compare which is the longer.

That's why we use the max(r, l) to compare which is the depth of tree.

 

Time complexity: O(N)

Space complexity: O(N)

Solution2(Binary Tree):

BST(queue) Method

Let's say q is the queue, levels is a pointer to point the depth of tree.

We have a queue, and we are trying to add the Child node to the queue. 

In example 1, we figure 3 has child nodes(9, 20). After add the child node, we add 1 to level.

At the point of 3, it would be 1.

 

Time complexity: O(N)

Space complextiy: O(N)