在这里插入图片描述

方法一 深度优先遍历 递归（栈）

# 遍历二叉树有两种 深度优先遍历   层序优先遍历

# 递归的实现调用自身的函数 都在缓存中，还没有执行  直到递归截至条件，从最后的函数进行执行
# 先进后出 就是栈的一个规律，进行执行的， 进就是调用函数本身 ，出就是递归截止条件后，执行之前的函数功能
# 左子树 深度   右子树深度   ，最大值  +1

# 递归的顺序方向  是入栈 ，开辟了缓存空间， 是多个 调用函数本身（空间换时间的方法）
# 递归的逆向就是执行 出栈， 从递归的截止条件（初始位置） 开始向上执行（
# 调用函数（调用的是自己） 

# .理解递归的时候不能一直往深处考虑，那样不适合人类的思维，只需要思考最后该退出时要返回什么，一般的情况下该返回什么，写代码时明确了这两个即可  （递归截止条件和 递归执行条件）
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: 
            return 0  #递归到底的情况需要写出来，这里也是初始化条件， 程序从这里向上执行
        else:
            return max(self.maxDepth(root.left),self.maxDepth(root.right))+1  
            

如下树的执行过程

框的位置  相当于递归的顺序执行 是 入栈操作
蓝色 是出栈运行， 递归截止 条件处 （ 同时也是程序初始执行结果） 开始执行 ，往上调用  
最后返回树的高度 3

在这里插入图片描述
在这里插入图片描述

方法2 层序遍历 队列

实际也不算是 队列， 就是 变量的循环更新 操作
记录一层所有的节点 queue ， while 不是空就 累加一层

# 层序遍历通常用  队列
# 深度优先遍历  栈（递归） 操作 

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
            if not root :
                return 0  #空 数的深度0
            queue=[root]
            res = 0
            # queue 每次存储的是 每一层所有的节点， 也就是上一层节点的所有 左右子节点
            # 变化 [3]  [9,20]    [15,7]   [最后是空的]
            #外层循环是 层数   内层循环是 每一层的节点遍历
            while queue:  #队列这里是动态变化的，空，跳出循环

                res = res+1  #res 是跟着 外层循环while走的， 

                # queue 每次变化 是每一层的节点， 直到 为空结束
                tmp = []  #用来临时储存  当前层 的 下一层所有节点
                for node in queue:#每个节点都要有，因为可能一层当中 都是上一层的左节点或者右节点
                    if node.left : tmp.append(node.left)
                    if node.right : tmp.append(node.right)
                
                queue = tmp
            return  res
                
# 参考         
# 作者：jyd
# 链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这里可能有个疑问 queue = [root] 初始化怎么是3不是所有节点昵

打印一下这里的queue
[TreeNode{val: 3, left: TreeNode{val: 9, left: None, right: None}, right: TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}}]

就是所有节点，树的结构
queue 实际更新的是 当前层 以及以下的所有层的节点
节点是一层层减少的 直到最后 得到所有的空节点，没有层了