怎么求出python二叉树的最大深度

发布时间：2021-12-13 16:04:40 阅读：172 作者：柒染栏目：大数据

Python开发者专用服务器限时活动，0元免费领，库存有限，领完即止！点击查看>>

本篇文章为大家展示了怎么求出python二叉树的最大深度，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

题目描述

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

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]，

    3   / \  9  20    /  \   15   7

返回它的最大深度 3 。

解题方案

思路

标签：DFS
找出终止条件：当前节点为空
找出返回值：节点为空时说明高度为0，所以返回0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值
某层的执行过程：在返回值部分基本已经描述清楚
时间复杂度：O(n)

代码

Java版本

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public int maxDepth(TreeNode root) {        if(root == null) {            return 0;        } else {            int left = maxDepth(root.left);            int right = maxDepth(root.right);            return Math.max(left, right) + 1;        }    }}

JavaScript版本

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number} */var maxDepth = function(root) {    if(!root) {        return 0;    } else {        const left = maxDepth(root.left);        const right = maxDepth(root.right);        return Math.max(left, right) + 1;    }};