本系列是代码随想录算法训练营的学习笔记之day16，主要记录一下刷题的过程，以及核心知识点和一些值的记录的问题。
代码随想录的资源可以看参考链接【1】。
今日知识点
二叉树基础：
- 二叉树中的几个关键词：结点、度、叶子结点
- 二叉树的两种主要形式包括满二叉树和完全二叉树
- 满二叉树只有度为0和度为2的结点；
- 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
- 二叉搜索树：有序树，左子树上所有节点的值小于根结点的值，右子树上所有节点的值大于根结点的值；
- 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
- 二叉树的储存方式：链式存储
用数组存储的二叉树如何遍历呢？如果父节点的下标是i，则左孩子是2i+1，右孩子是2i+2；
-
二叉树的遍历方式主要有深度优先遍历和广度优先遍历：
- 深度优先：前序遍历、中序遍历、后序遍历；
- 广度优先：层次遍
- 其他的更多理论基础可以去看参考链接【2】；
今日题目
- 二叉树的最大深度（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
- 二叉树的最小深度（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
- 完全二叉树的结点个数（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
补充知识点
- collections.deque()
collections模块是python内置的模块之一，实现了常见的数据结构，deque是双项队列，具体见参考【2】。
- queue.popleft()
移去并且返回一个元素，deque 最左侧的那一个。 如果没有元素的话，就引发 IndexError。
今日思考
- 为什么类方法的第一个参数需要为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
本文由mdnice多平台发布
