Description: Given the root of a binary tree, return its maximum depth.
A binary tree‘s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Link: 104. Maximum Depth of Binary Tree
Examples:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2: Input: root = [1,null,2] Output: 2 Example 3: Input: root = [] Output: 0 Example 4: Input: root = [0] Output: 1
思路: 深度优先搜索所有路径，收集所有路径的深度，返回最大的深度。
class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ path = [] self.dfs(root, 0, path) return max(path) def dfs(self, node, length, path): if node is None: path.append(length) return else: length += 1 self.dfs(node.left, length, path) self.dfs(node.right, length, path)
但是很显然这样的方式浪费了不必要的存储空间，参考了一篇博客的DFS解题思路，很巧妙，很美。
class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if root is None: return 0 else: return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
日期: 2021-03-12
Leetcode 104. Maximum Depth of Binary Tree
原文：https://www.cnblogs.com/wangyuxia/p/14526002.html