本系列是代码随想录算法训练营的学习笔记之day16，主要记录一下刷题的过程，以及核心知识点和一些值的记录的问题。

代码随想录的资源可以看参考链接【1】。

今日知识点

二叉树基础：

• 二叉树中的几个关键词：结点、度、叶子结点
• 二叉树的两种主要形式包括满二叉树和完全二叉树

• 满二叉树只有度为0和度为2的结点；
• 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

• 二叉搜索树：有序树，左子树上所有节点的值小于根结点的值，右子树上所有节点的值大于根结点的值；

• 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

• 二叉树的储存方式：链式存储

• 用数组存储的二叉树如何遍历呢？如果父节点的下标是i，则左孩子是2i+1，右孩子是2i+2；

• 二叉树的遍历方式主要有深度优先遍历和广度优先遍历：

  • 深度优先：前序遍历、中序遍历、后序遍历；
  • 广度优先：层次遍

• 其他的更多理论基础可以去看参考链接【2】；

今日题目

1. 二叉树的最大深度（104）

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/

解题思路

• 递归法理解起来更简单；

• 要注意根结点的深度为1，其高度就等于整个树的深度；

• 递归法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        max_l = self.maxDepth(root.left)
        max_r = self.maxDepth(root.right)
        return 1+max(max_l,max_r)

• 结束递归的条件为root为空，也可以写root==None；

• 要使用self.maxDepth()来递归调用函数；

• 迭代法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import collections
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        depth = 0 #记录深度
        queue = collections.deque()
        queue.append(root)
        while queue:
            size = len(queue)
            depth += 1
            for i in range(size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return depth

2. 二叉树的最小深度（111）

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/

解题思路

• 仍然用递归的方法

• 递归法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root==None:
            return 0
        if not root.left and not root.right:
            return 1
        
        min_d = 1e9
        if root.left:
            min_d = min(self.minDepth(root.left),min_d)
        if root.right:
            min_d = min(self.minDepth(root.right),min_d)
        return min_d+1

• 结束递归的条件为root为空，也可以写root==None；

• 结束递归的条件要注意不要忘记了只有当前结点，没有子结点的情况；

• 迭代法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        que = deque()
        que.append(root)
        res = 1

        while que:
            for _ in range(len(que)):
                node = que.popleft()
                # 当左右孩子都为空的时候，说明是最低点的一层了，退出
                if not node.left and not node.right:
                    return res
                if node.left is not None:
                    que.append(node.left)
                if node.right is not None:
                    que.append(node.right)
            res += 1
        return res

3. 完全二叉树的结点个数（222）

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/count-complete-tree-nodes/

解题思路

• 首先要清楚的知道完全二叉树的定义，其特点是如果对完美二叉树按照从上至下、从左到右的顺序编号，则完全二叉树中对应结点的序号与完美二叉树中的序号一致；

• 递归法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        return self.getNodes(root)
    
    def getNodes(self,cur):
        if cur==None:
            return 0
        cnt_l = self.getNodes(cur.left)
        cnt_r = self.getNodes(cur.right)

        return cnt_l+cnt_r+1

• 只要中间的结点不为None，节点数目就要加上1；
• getNodes()的参数一定要有self；
• 下面这种递归更像递归：

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

• 迭代法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import collections
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        queue = collections.deque()
        if root:
            queue.append(root)
        result = 0
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                result += 1 #记录节点数量
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

补充知识点

1. collections.deque()

collections模块是python内置的模块之一，实现了常见的数据结构，deque是双项队列，具体见参考【2】。

2. queue.popleft()

移去并且返回一个元素，deque 最左侧的那一个。 如果没有元素的话，就引发 IndexError。

今日思考

1. 为什么类方法的第一个参数需要为self？

如果不写self的话，就会报错如下：

所以，第一个不写self的话会报错！

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        return self.getNodes(root)
    
    def getNodes(self,cur):
        if cur==None:
            return 0
        cnt_l = self.getNodes(cur.left)
        cnt_r = self.getNodes(cur.right)

        return cnt_l+cnt_r+1

实际上self代表的是类对象本身， 比如上面的代码，如果不把self传给getNodes函数，那么在getNodes中就无法调用getNodes函数。。。是有点绕口，但是理解了就好。

今日吐槽

百度上搜索一个问题，你们这些垃圾抄过来抄过去，都不看一下答案吗？那答案你们能看懂吗！！就知道cp，就不知道动动脑子！！！

是在下错了，不该用中文搜索。

参考

【1】代码随想录：https://programmercarl.com/
【2】collections：https://docs.python.org/zh-cn/3/library/collections.html?highlight=deque