[剑指 Offer 第 2 版第 55-1 题] “二叉树的深度”做题记录

第 55-1 题：二叉树的深度

传送门：二叉树的深度，牛客网 online judge 地址。。

输入一棵二叉树的根结点，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

样例：

输入：二叉树 [8, 12, 2, null, null, 6, 4, null, null, null, null] 如下图所示： 8 / \ 12 2 / \ 6 4 输出：3

思路：使用广度优先遍历。

Python 代码：

  class Solution:
        def treeDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """

            if root is None:
                return 0

            queue = [(1, root)]
            res = 0
            while queue:
                top = queue.pop(0)
                cur_depth, node = top[0], top[1]
                res = max(res, cur_depth)
                if node.left:
                    queue.append((cur_depth + 1, node.left))
                if node.right:
                    queue.append((cur_depth + 1, node.right))
            return res

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/