leetcode | 104.二叉树的最大深度

104.二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，

题目链接

思路

方法一：深度优先搜索
首先可以想到使用深度优先搜索的方法，遍历整棵树，记录最小深度。
对于每一个非叶子节点，我们只需要分别计算其左右子树的最大叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。

代码

# class TreeNode(object):  # Definition for a binary tree node.
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def get_depth(root):
            if not root:
                return 0
            left_depth = get_depth(root.left)
            right_depth = get_depth(root.right)
            return max(right_depth, left_depth) + 1
        return get_depth(root)