树1 二叉树的最大深度

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

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

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

示例：

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

    3

  / \

  9  20

    /  \

  15  7

返回它的最大深度 3 。

1、思路1:递归+深度优先搜索

代码如下：

class Solution:

    def maxDepth(self, root: TreeNode) -> int:

        if root is None: 

            return 0 

        else: 

            left_height = self.maxDepth(root.left) 

            right_height = self.maxDepth(root.right) 

            return max(left_height, right_height) + 1 

2、广度优先搜索

遍历每一层，重要的是 二叉树的截止搜索条件:所有子节点的子节点都为空

代码如下：

# 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:

        if root is None: 

            return 0 

        tmp=deque([root])

        level=0

        while tmp:

            n=len(tmp)

            #node=tmp.popleft()

            for i in range(n):

                node = tmp.popleft()

                if node.left is not None:

                    tmp.append(node.left)

                if node.right is not None:

                    tmp.append(node.right)

            level=level+1

        return level

参考资料：

1、二叉树的最大深度

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/python-3di-gui-zi-ding-xiang-xia-zi-di-xiang-shang/