今日任务：
1）104.二叉树的最大深度
2）559.n叉树的最大深度
3）111.二叉树的最小深度
4）222.完全二叉树的节点个数
104.二叉树的最大深度
题目链接：104. 二叉树的最大深度 - 力扣（LeetCode）
给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
文章讲解：代码随想录 (programmercarl.com)
视频讲解：二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | LeetCode：104.二叉树的最大深度哔哩哔哩bilibili
思路：
这道题已经在前一篇文章算法打卡day13层序遍历中做过了，如果采用迭代的方法，就用层序遍历，这题比较简单，遍历完所有节点，每遍历一层深度加一即可
今天采用递归（后序遍历）的方法来做，也可以用前序遍历来做（前序遍历涉及到回溯，我还不理解，等后序二刷再来研究），前序遍历求的就是深度，后序遍历求的是高度
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
其实弄懂这两个概念，就会发现，在此题求二叉树最大深度中，高度与深度可与转换，当我求二叉树最大深度，也就是最底层叶子节点的深度，也就根节点的高度，所以我们求二叉树最大深度可以转换为，求根节点的高度
求高度我们用后序遍历（左右中），后序遍历是找到叶子节点，然后按左右中每次往上遍历，到中时，需要取左数与右树的最大深度
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: [TreeNode]) -> int:
return self.getHeight(root)
def getHeight(self,node):
if not node:
return 0
leftDepth = self.getHeight(node.left) # 左
rightDepth = self.getHeight(node.right) # 右
height = 1 + max(leftDepth, rightDepth) # 中
return height感想：
这题想清楚了就比较简单，最直截了当的就是层序遍历，递归的方法不好想一点，做之前可能要区分高度与深度，但做完就能跳出深度与高度的概念，后序从下网上，就是从下开始计数，前序从上往下遍历，就是从上开始计数
559.n叉树的最大深度
题目链接：559. N 叉树的最大深度 - 力扣（LeetCode）
给定一个 n 叉树，找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
文章讲解：代码随想录 (programmercarl.com)
思路：
如果采用迭代，层次遍历，这题与上一题一样只是左右节点换成孩子节点了，其他一样
这题如果采用递归的方法，我们也是采用后序遍历
求二叉树深度，我们只需要求出左右树的深度，然后比较，取最大。但是在N叉树中，我们不知道有几个子树，我们需要遍历子树，并用变量记录最大高度，每求一棵树的高度，变与变量比较，将大值重新赋给变量
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
class Solution:
def maxDepth(self, root: Node) -> int:
return self.getHeight(root)
def getHeight(self,node: Node):
if not node:
return 0
height = 0
for child in node.children:
height = max(height,self.getHeight(child))
return height + 1111.二叉树的最小深度
题目链接：111. 二叉树的最小深度 - 力扣（LeetCode）
给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 这题在02二叉树的层序遍历中做过，采用的层次遍历
文章讲解：代码随想录 (programmercarl.com)
视频讲解：看起来好像做过，一写就错！ | LeetCode：111.二叉树的最小深度哔哩哔哩bilibili
思路：
做了前面几题，这题思路比较好像，递归后序遍历，取左右子树的最小高度即可，但这里面有个坑
最小深度是要找根节点到最近叶子节点的距离，注意是叶子节点，也就就是得遇到左右节点均为空才算遇到了叶子节点
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:
return self.getDepth(root)
def getDepth(self, node):
# 排除左右节点均为空
if not node:
return 0
leftDepth = self.getDepth(node.left)
rightDepth = self.getDepth(node.right)
# 注意，叶子节点是需要左右都为空才为叶子节点
if node.left == None and node.right:
depth = rightDepth + 1
elif node.right == None and node.left:
depth = leftDepth + 1
# 现在还剩左右均不为空的情况
else:
depth = 1+ min(rightDepth,leftDepth)
return depth感想：
以上这两题得递归我写的比较复杂，但是好理解，所以没有放上精简版，如果后面自己熟练了二叉树递归，我在补充上精简版
222.完全二叉树的节点个数
题目链接：222. 完全二叉树的节点个数 - 力扣（LeetCode）
给出一个完全二叉树，求出该树的节点个数。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6示例 2：
输入：root = []
输出：0
示例 3：输入：root = [1]
输出：1
提示：
树中节点的数目范围是[0, 5 * 10^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是 完全二叉树
文章讲解：代码随想录 (programmercarl.com)
视频讲解：要理解普通二叉树和完全二叉树的区别！ | LeetCode：222.完全二叉树节点的数量哔哩哔哩bilibili
二叉树求节点个数统一思路：
这题有两个思路，不管什么二叉树求节点个数，我们可以用迭代层序遍历，或者递归后序遍历，遍历完计数即可，这样会把每个节点遍历一遍
- 时间复杂度：O(n)
- 空间复杂度：O(log n)
lass 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: [TreeNode]) -> int:
return self.getNum(root)
def getNum(self,node):
if not node:
return 0
leftNum = self.getNum(node.left)
rightNum = self.getNum(node.right)
totalNode = leftNum + rightNum + 1
return totalNode完全二叉树求节点个数思路
对于完全二叉树，我们的遍历过程可以简化，不用遍历所有节点，我们只需要找出二叉树中的满二叉树，满二叉树知道其深度k，可以利用公式2^k-1得到节点个数
- 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
- 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
如果是满二叉树，直接求节点，如果不是，则需要分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
那么如何判断某个树是不是满二叉树
我们只需要判断树的左右最外层是否相等
如，这一种就不等
继续往下找
左边已经找到，计算节点即可，右边继续
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: [TreeNode]) -> int:
return self.getNum(root)
def getNum(self,node):
if not node:
return 0
left = node.left
leftDepth = 1
right = node.right
rightDepth = 1
# 求左子树深度
while left:
left = left.left
leftDepth += 1
# 求右子树深度
while right:
right = right.right
rightDepth += 1
if leftDepth == rightDepth:
return 2**leftDepth - 1
return self.getNum(node.left) + self.getNum(node.right) + 1感想：
这题需要自己多画画图，搞清楚完全二叉树概念，下次碰到，不能想到，就用最直接的二叉树统一方法，能够做出来是第一步，优化是第二步
