二叉树的最大深度 |
您所在的位置：网站首页 › 二叉树深度算法递归 › 二叉树的最大深度 |
二叉树的最大深度
|
题目来源于力扣，如下： 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7] 对于一个具有n个节点的二叉树，需要调用函数2n+1次访问其扩充二叉树全部结点，尾递归方式开辟临时空间n个用于变量存储，时间复杂度O(n)空间复杂度O(n) def maxDepth2(root: TreeNode) -> int: return 0 if root == None else max([maxDepth2(root.left), maxDepth2(root.right)]) + 1 算法二：非递归方式利用宽度优先搜索方式，创建两个队列分别用于存储当前层和下一层结点，对n个结点需遍历n次，循环内各操作时间复杂度均为O(1)，故总体时间复杂度为O(n);两队列最多需要存储n/2个结点数据，空间复杂度O(n) def maxDepth(root: TreeNode) -> int: if root is None: return 0 depth = 1 q1, q2 = [], [] # 先进先出队列 q1.append(root) while q1 != [] or q2 != []: if q1 == []: depth +=1 q1, q2 = q2, q1 root = q1.pop(0) if root.left is not None: # 将非空的左右子树存入队列 q2.append(root.left) if root.right is not None: q2.append(root.right) return depth |
返回它的最大深度 3 。【本文地址】
今日新闻 |
推荐新闻 |