给定一个二叉树，找出其最大深度。(老规矩前两个我写的,后面我抄的,尤其是最后一个递归真是经典)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        这个是根据maxDepth1,将maxDepth2改进的
        :type root: TreeNo de
        :rtype: int
        """
        if not root:
            return 0

        queue = [root]
        count = 0
        while queue:
            count += 1
            size = len(queue)
            for i in range(size):
                node_ = queue.pop(0)
                if node_ and node_.left:
                    queue.append(node_.left)
                if node_ and node_.right:
                    queue.append(node_.right)
        return count

    def maxDepth2(self, root):
        """
        如果直接给出数组的长度,可以通过满二叉树的节点公式2**n -1(n表示层数,公式整体算出来的所有节点数)
        但是这个没有所以都要经过遍历直接使用队列,类似于
        :type root: TreeNo de
        :rtype: int
        """
        if not root:
            return 0

        queue = [root]
        ret_list = []
        while queue:
            size = len(queue)
            inner_list = []
            for i in range(size):
                node_ = queue.pop(0)
                inner_list.append(node_)
                if node_ and node_.left:
                    queue.append(node_.left)
                if node_ and node_.right:
                    queue.append(node_.right)
            ret_list.append(inner_list)
        return len(ret_list)

    def maxDepth1(self, root):
        """
        这个挺好直接深度遍历使用一个变量统计层数就可以了,看来我的代码还可以改改
        :type root: TreeNode
        :rtype: int
        """
        # bfs
        if not root:
            return 0
        else:
            queue = [(1, root)]
            while queue:
                depth, node = queue.pop(0)
                if node.left:
                    queue.append((depth + 1, node.left))
                if node.right:
                    queue.append((depth + 1, node.right))
        return depth

    def maxDepth3(self, root):
        """
        内存消耗最少,经典递归*****
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        else:
            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

if __name__ == '__main__':
    s1 = Solution()
    head = [4, 5, 1, 9]; node = 1
    s1.maxDepth(head, node)