电商类网站开发合同书,wordpress图片生成插件下载,响应式网站建设原则,沼气服务网站建设管理二叉树的最大深度
给定一个二叉树 root #xff0c;返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例1 输入#xff1a;root [3,9,20,null,null,15,7] 输出#xff1a;3
解题思路
二叉树的最大深度可以通过递归方式来求解…二叉树的最大深度
给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例1 输入root [3,9,20,null,null,15,7] 输出3
解题思路
二叉树的最大深度可以通过递归方式来求解。
1、如果二叉树为空返回深度0。2、递归地求解左子树和右子树的最大深度。3、返回左右子树中的最大深度加上当前节点的深度1。
Java实现
public class MaxDepthOfBinaryTree {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;}}public int maxDepth(TreeNode root) {// 递归结束条件if (root null) {return 0;}// 递归计算左子树和右子树的最大深度int leftDepth maxDepth(root.left);int rightDepth maxDepth(root.right);// 返回左右子树中的较大深度加上当前节点return Math.max(leftDepth, rightDepth) 1;}public static void main(String[] args) {// 构造一个二叉树TreeNode root new TreeNode(1);root.left new TreeNode(2);root.right new TreeNode(3);root.left.left new TreeNode(4);root.left.right new TreeNode(5);// 创建 MaxDepthOfBinaryTree 对象MaxDepthOfBinaryTree solution new MaxDepthOfBinaryTree();// 计算二叉树的最大深度int depth solution.maxDepth(root);// 打印结果System.out.println(Max Depth of Binary Tree: depth);}
}
时间空间复杂度
时间复杂度O(n)其中n是二叉树中的节点数每个节点都需要访问一次。空间复杂度O(height)其中height是二叉树的高度递归调用栈的深度。
