"""
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。
"""

class Solution(object):
    # 基于迭代的方式
    def maxDepth(self, root):
        if not root: return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

    #基于bst(广度优先遍历算法)
    def maxDepth(self, root):
        if not root: return 0
        res = 0
        queue = []
        queue.append(root)
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue[0]
                queue.remove(node)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res += 1
        return res