第九天 Maximum Depth Of Binary Tree

哈哈，还在SB似的坚持着，难得呀，对于我这种“三分钟”热度的人来说

当然也是因为我开始一直刷水题吧

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/

计算二叉树的最大深度，直接想到的就是DFS，那么最简单和明了的方法，就是递归咯，基于系统栈。

# 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):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))

思路就是
1、先看当前节点是否存在，如果是的话，高度+1
2、然后同样的方法计算左子树的最大深度和右子树的最大高度，如果没有，那么就是说左子树的高度为0咯
3、根据题意，左右子树最大高度+1（即根结点的），就是这颗树的最大高度咯

递归的思想，也是我一直觉得非常“精巧”的一种思路，甚至有那么点“难以捉摸” 😂

那么除了DFS之外，还有一种BFS，趁着这道题不难，那么也来写一下吧：

# 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):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        depth = 0
        q = [root]
        while len(q) != 0:
            depth += 1
            for i in range(0,len(q)):
                if q[0].left:
                    q.append(q[0].left)
                if q[0].right:
                    q.append(q[0].right)
                del q[0]
        return depth

利用队列先进先出的特性，其实也是实现了一个树的按层次遍历。那么没遍历到新的一层，就是高度+1的节奏了，其实这里的高度也就是层数的意思，道理是这么个道理，但明白了，还能准确的写出代码，还是要多思考多练习

这里对于Python的队列用法还是“蛮粗糙”的，哎，基础不好啊