企业官网建设流程全解析

二叉树的最大深度

题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public int maxDepth(TreeNode root) { if(root==null){ return 0; } int leftMax, rightMax; leftMax = maxDepth(root.left); rightMax = maxDepth(root.right); return 1+Math.max(leftMax,rightMax); }

分析：代码的时间复杂度为O(n)，空间复杂度为O(height)，其中 height 表示二叉树的高度。解题思路：采用递归，每次递归计算当前节点的左右子树的最大深度，而当前节点的最大深度就是左右子树的最大深度加一。

看了官方题解后的解答：

//方法一：深度优先搜索 （思路与我的解答相同） //方法二：广度优先搜索 //时间复杂度：O(n) //空间复杂度：O(n) public int maxDepth(TreeNode root) { if(root==null){ return 0; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int ans=0; while(!queue.isEmpty()){ int size=queue.size(); while(size>0){ TreeNode node = queue.poll(); size--; if(node.left!=null){ queue.offer(node.left); } if(node.right!=null){ queue.offer(node.right); } } ans++; } return ans; }

分析：

​ 1、方法一采用深度优先搜索。通过递归计算当前节点左右子树的最大深度来计算当前节点的最大深度。

​ 2、方法二采用广度优先搜索。通过队列保存每一层所有节点，从而计算二叉树的最大深度。

总结

• 本题主要利用深度优先搜索和广度优先搜索方法来计算二叉树的最大深度。