LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )

简介: LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容,和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣!

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

题目描述

给定一个二叉树,找出其最大深度。

最大深度是从根节点到最远叶子节点的最长路径上的节点数。

示例:

给定二叉树 [3,9,20,null,null,15,7]

3
   / \
  9  20
    /  \
   15   7

最大深度是 3。

方法一:递归

解题步骤

  1. 如果节点为空,返回深度 0。
  2. 递归计算左子树的最大深度。
  3. 递归计算右子树的最大深度。
  4. 返回左右子树深度的最大值加一(当前节点的深度)。

Python 示例

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

算法分析

  • 时间复杂度:O(N),其中 N 为树的节点数,每个节点访问一次。
  • 空间复杂度:O(H),其中 H 为树的高度,因为递归栈的深度由树的高度决定。

算法图解与说明

3            <-- Level 1
 / \
9  20          <-- Level 2
  /  \
 15   7        <-- Level 3
调用栈情况(以节点3为例):
maxDepth(3)
=> maxDepth(9), maxDepth(20)
   => maxDepth(null), maxDepth(null), maxDepth(15), maxDepth(7)

方法二:迭代(使用栈)

解题步骤

  1. 使用栈来模拟递归过程,每个元素为节点及其当前深度。
  2. 初始化栈包含根节点和深度 1。
  3. 当栈不为空,弹出节点并更新最大深度。
  4. 将节点的左右子节点及其深度压入栈中。

Python 示例

def maxDepthIterative(root):
    if not root:
        return 0
    stack = [(root, 1)]
    max_depth = 0
    while stack:
        node, depth = stack.pop()
        if node:
            max_depth = max(max_depth, depth)
            stack.append((node.left, depth + 1))
            stack.append((node.right, depth + 1))
    return max_depth

算法分析

  • 时间复杂度:O(N)
  • 空间复杂度:O(N)

算法图解与说明

栈的操作示例:
初始: [(3, 1)]
操作: 弹出(3, 1), 压入(9, 2), 压入(20, 2)
接着: 弹出(20, 2), 压入(15, 3), 压入(7, 3)
接着: 弹出(7, 3), 弹出(15, 3), 弹出(9, 2)

方法三:层序遍历(使用队列)

解题步骤

  1. 使用队列实现层序遍历。
  2. 每遍历完一层,深度加一。

Python 示例

from collections import deque
def maxDepthUsingBFS(root):
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

算法分析

  • 时间复杂度:O(N)
  • 空间复杂度:O(N)

算法图解与说明

队列操作示例:
初始: [3]
操作: 弹出3, 压入9, 压入20
接着: 弹出9, 弹出20, 压入15, 压入7
接着: 弹出15, 弹出7

方法四:尾递归优化

解题步骤

  1. 使用尾递归形式来优化递归的性能。
  2. 传递当前深度作为参数,避免额外的递归开销。

Python 示例

def maxDepthTailRecursive(root, depth=0):
    if not root:
        return depth
    return max(maxDepthTailRecursive(root.left, depth + 1), maxDepthTailRecursive(root.right, depth + 1))

算法分析

  • 时间复杂度:O(N)
  • 空间复杂度:O(H),利用尾递归优化,Python 中不一定有效,取决于解释器是否优化尾调用。

算法图解与说明

递归调用栈(尾递归):
maxDepthTailRecursive(3, 0)
=> maxDepthTailRecursive(9, 1), maxDepthTailRecursive(20, 1)
   => maxDepthTailRecursive(null, 2), ...

方法五:分治法

解题步骤

  1. 对每个节点,分别求解左右子树的最大深度。
  2. 合并左右子树深度的结果,取最大值加一。

Python 示例

def maxDepthDivideAndConquer(root):
    if not root:
        return 0
    left_depth = maxDepthDivideAndConquer(root.left)
    right_depth = maxDepthDivideAndConquer(root.right)
    return 1 + max(left_depth, right_depth)

算法分析

  • 时间复杂度:O(N)
  • 空间复杂度:O(H)

算法图解与说明

分治递归过程:
maxDepthDivideAndConquer(3)
=> maxDepthDivideAndConquer(9), maxDepthDivideAndConquer(20)
   => maxDepthDivideAndConquer(null), maxDepthDivideAndConquer(null), ...

应用示例

上述各方法均适用于任何形式的二叉树结构,可以有效解决实际问题中的深度计算问题。

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️作者知识有限,如有错误,请各位大佬评论区批评指正,不胜感激❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
13天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
12 3
|
23天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
8天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
1月前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
1月前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题