来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/，接下来我们就来聊聊关于二叉树的常用算法怎么写?以下内容大家不妨参考一二希望能帮到您!

二叉树的常用算法怎么写（104.二叉树的最大深度）

二叉树的常用算法怎么写

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

题目描述

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

题目分析

提供两种方法实现：

  • BFS（Breath First Search）广度优先搜索
  • DFS（Deep First Search）深度优先搜索
代码实现

public class MaxDepth104 { public static void main(String[] args) { MaxDepth104 maxDepth = new MaxDepth104(); TreeNode root = new TreeNode(1, new TreeNode(10), new TreeNode(2, new TreeNode(3), new TreeNode(9, null, new TreeNode(4)))); maxDepth.maxDepth(root); maxDepth.maxDepth2(root); } /** * 广度优先算法 * * @param root * @return */ public int maxDepth2(TreeNode root) { if (root == null) { return 0; } int depth = 0; Queue<TreeNode> queue = new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i ) { TreeNode curr = queue.poll(); if(curr.left != null){ queue.offer(curr.left); } if(curr.right != null){ queue.offer(curr.right); } } depth ; } return depth; } /** * 前序遍历 深度优先算法 * <p> * 时间复杂度：O(n)，其中 nnn 为二叉树节点的个数。每个节点在递归中只被遍历一次。 * <p> * 空间复杂度：O(height)，其中 height\textit{height}height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。 * * @param root * @return */ public int maxDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); int maxDepth = Math.max(leftDepth, rightDepth) 1; System.out.println(maxDepth); return maxDepth; } }

BFS复杂度
  • 时间复杂度：O(n)
  • 空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)
DFS复杂度
  • 时间复杂度：O(n)
  • 空间复杂度：O(height)，其中 height 表示二叉树的高度

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！

,