Ang Li

Leetcode题解 104: Maximum Depth of Binary Tree

2020/04/03

题目内容

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

题目样例

Example:

Given binary tree [3,9,20,null,null,15,7]

   3
  / \
 9  20
   /  \
  15   7

return its depth = 3

题目分析

简单的二叉树入门问题，用递归的思想来解题。对于单个节点Node来说，以其为根的树的最深高度等于其左子树与右子树深度的最大值加一。所有的递归运算都有出口，本题需要考虑当node的值为None时，返回0。

举例说明

我们有一下一棵二叉树：

为了求根部1的最大深度，我们需要求出3和高度H(Node(3)) 和H(Node(11))

求出的高度 Max（H(Node(3))， H(Node(11))）+ 1就是点本身的最深高度

当点为None时，递归找到出口。

img

代码实现

Python

def maxDepth(self, root):
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

注意事项

  1. 对于递归算法 最先要考虑的是递归的出口
  2. 对于二叉树上的递归，应该考虑根节点和左右两个节点的关系

复杂度

时间复杂度：O(log(n))

空间复杂度：O(n)

相似题目

Post Directory