网络异常,图片无法展示
|
题目地址(55 - I. 二叉树的深度)
题目描述
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 提示: 节点总数 <= 10000 注意:本题与主站 104 题相同:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
思路
用dfs的方式进行递归遍历,找出全部点,然后通过当前深度,和最大深度的max比较,返回最大深度
关键点
代码
- 语言支持:Python3
Python3 Code:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def maxDepth(self, root: TreeNode) -> int: res = self.dfs(root,0,0) return res def dfs(self, node: TreeNode, cur: int, maxNum: int)->int: if node == None: # print("尽头",cur,maxNum) return maxNum cur = cur+1 # print(node.val, cur,maxNum) maxNum = max(maxNum, cur) leftMax, rightMax = 0, 0 if node.left != None: leftMax = self.dfs(node.left,cur,maxNum) if node.right != None: rightMax =self.dfs(node.right,cur,maxNum) # print("max",leftMax,rightMax) return max(leftMax,rightMax,maxNum)
复杂度分析
令 n 为数组长度。
- 时间复杂度:O(n)O(n)
- 空间复杂度:O(n)O(n)