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.
Solution 1: recursive
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
l = self.maxDepth(root.left)
r = self.maxDepth(root.right)
res = 1 + max(l, r)
return res
Solution 2: iterative (Depth first search, using stack)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = 0
stack = [(root, 0)]
if not root:
return res
while stack:
node, depth = stack.pop()
if node.right:
stack.append((node.right, depth + 1))
if node.left:
stack.append((node.left, depth + 1))
res = max(res, depth + 1)
return res