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 = NoneclassSolution(object):defmaxDepth(self,root):""" :type root: TreeNode :rtype: int """ifnot root:return0 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 = NoneclassSolution(object):defmaxDepth(self,root):""" :type root: TreeNode :rtype: int """ res =0 stack = [(root,0)]ifnot root:return reswhile 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