一、110.平衡二叉树
再一次涉及到，什么是高度，什么是深度，可以巩固一下。题目链接/文章讲解/视频讲解：代码随想录
1. 整体逻辑
一棵高度平衡二叉树定义为平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。通过比较两两左右子树的高度差是否小于等于1，来判断该树是否是一颗平衡二叉树。
由于该题是判断高度差，也就是自下而上，所以采用后序遍历，在比较完子树之后将结果传递给父节点，因此必须采用后序遍历。
2. 具体逻辑
（1）终止条件：如果一个节点的子节点是空，那么说明这个节点是叶子节点，而叶子节点的高度是0，所以返回0。
（2）后序遍历：左右中的顺序。
1）左：利用递归法计算左子树的高度，如果左子树返回值为-1，说明左子树本身不是平衡二叉树，那么也返回一个-1即可。（检查左右子树是否满足平衡二叉树）
2）右：利用递归法计算右子树的高度，如果右子树返回值为-1，说明右子树本身不是平衡二叉树，那么也返回一个-1即可。（检查左右子树是否满足平衡二叉树）
3）中：当左右子树均满足平衡二叉树，此时需要对左右子树的高度差进行检查，是否小于等于1，因此定义一个变量来计算左右子树高度差。如果左右子树的高度差小于等于1，那么计算当前父节点的高度，等于取左右子树最大值+1。
（3）最后在主函数调用即可，返回布尔值。
3. 完整代码
class Solution:
def isBalanced(self, root: Optional[TreeNode])->bool:
res = self.getHeight(root)
if res == -1:
return False
else:
return True
def getHeight(self, root: TreeNode)->int:
if root is None:
return 0
# left:
l_height = self.getHeight(root.left)
if l_height == -1:
return -1
# right:
r_height = self.getHeight(root.right)
if r_height == -1:
return -1
# middle:
height = abs(r_height - l_height)
if height > 1:
return -1
else:
return max(l_height, r_height)+1注意：
错误思路如下：只判断相邻子树之间如果高度差大于1，则返回false，但平衡二叉树是指该树所有节点的左右子树的高度相差不超过 1，所以必须去计算所有节点的子树高度差均不大于1。
错误代码将下图这种情况判断为true，而实际上应该判断为false。
所以正确做法应该是去计算所有节点上左右子树的高度差，再进一步进行判断。
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
l_height = self.isBalanced(root.left)
r_height = self.isBalanced(root.right)
height = abs(l_height-r_height)
if height > 1:
return False
else: return True
二、257. 二叉树的所有路径
这是大家第一次接触到回溯的过程， 我在视频里重点讲解了 本题为什么要有回溯，已经回溯的过程。如果对回溯 似懂非懂，没关系， 可以先有个印象。
题目链接/文章讲解/视频讲解：代码随想录
1. 整体逻辑
本题目要求根节点到所有叶子节点的路径，所以从一条路径指向下一条路径会涉及到回溯，将遍历过的路径弹出，继续遍历下一个路径。此外，由于是从根节点出发，所以需要从父节点指向对应的孩子节点，从而寻找路径，所以必须采用前序遍历。
2. 具体逻辑
（1）首先定义一个回溯函数traversal，传入self、cur、path、result。cur用于遍历节点，表示当前父节点；path用于存放遍历过的路径；result用于存放结果集。
（2）前序遍历：中->左->右。
1）中：将当前父节点的值存放进当前路径中，然后判断是否到达叶子节点（如果当前父节点的左右孩子均为空，那么说明到达了叶子结点，也就是说这条路径遍历完成）。所以需要将这条完整的路径用‘ -> ’ 符号进行连接，并且需要将路径的每个元素转换为str形式，因为最后输出的形式为“List[str]”。接下来将这条路径存放进结果集中，并且返回。
sPath = '->'.join(map(str, path))
2）接下来进行左遍历：只要当当前父节点左孩子不为空，则一直调用递归函数进行遍历，最后pop出去即可。
3）最后进行右遍历：同左遍历。
（3）在主函数中，定义一个空数组path和result，判断传入的根结点不为空，然后调用递归函数traversal，最后返回结果。
3. 完整代码
class Solution:
def traversal(self, cur, path, result):
# middle:
path.append(cur.val)
if cur.left is None and cur.right is None:
sPath = "->".join(map(str, path))
result.append(sPath)
return
# left:
if cur.left:
self.traversal(cur.left, path, result)
path.pop()
# right:
if cur.right:
self.traversal(cur.right, path, result)
path.pop()
def binaryTreePaths(self, root):
result = []
path = []
if root is None:
return result
self.traversal(root, path, result)
return result三、404.左叶子之和
其实本题有点文字游戏，搞清楚什么是左叶子，剩下的就是二叉树的基本操作。题目链接/文章讲解/视频讲解：代码随想录
1. 整体逻辑
（1）确定判断逻辑：
左叶子 = 叶子节点（左右孩子均为空）+ 左（父节点的左孩子）
注意：不可以遍历到叶子节点才进行判断，因为无法知道是否是左孩子，只能知道是叶子节点，所以需要在遍历到父节点就开始对左孩子进行处理。
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
左叶子节点处理逻辑
}（2）选择遍历顺序：
收集左叶子之和一层层返回给父节点，所以最好使用后序遍历。
2. 具体逻辑
（1）如果遇到节点为空，那么其左叶子之和一定为空，所以返回0。如果遇到叶子节点（左孩子和右孩子为空），叶子节点不是我们要采集的值，因为无法知道是否是左孩子，并且叶子节点收集的是左右子树的和，其左右子树为空，所以返回0。
（2）后序遍历：
1）左：遍历左子树并收集所有符合左叶子条件的和， 如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，收集的元素就是该左叶子；
2）右：同左；
3）中：左树的左叶子和+右树的左叶子和，并返回左叶子总和。
3. 完整代码
# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if root is None: return 0
if root.left is None and root.right is None: return 0
# left:
leftvalue = self.sumOfLeftLeaves(root.left)
if root.left is not None and root.left.left is None and root.left.right is None:
leftvalue = root.left.val
# right:
rightvalue = self.sumOfLeftLeaves(root.right)
sum = leftvalue + rightvalue
return sum四、222.完全二叉树的节点个数
需要了解，普通二叉树 怎么求，完全二叉树又怎么求题目链接/文章讲解/视频讲解：代码随想录
1. 整体逻辑
（1）普通二叉树解法：
遍历左子树的所有节点和右子树的所有节点，两个子树节点相加，再加上根节点1即可。
（2）完全二叉树解法：
利用完全二叉树特性，终止条件有两个：一是根节点为空，而是左右子树存在满二叉树，则可以使用公式子树节点总数num=（2^层数）-1。
2. 完整代码
（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 countNodes(self, root: Optional[TreeNode]) -> int:
return self.getNodesNum(root)
def getNodesNum(self, cur):
if cur is None:
return 0
leftnum = self.getNodesNum(cur.left)
rightnum = self.getNodesNum(cur.right)
sum = leftnum + rightnum+1
return sum（2）完全二叉树解法：
# 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:
if root is None: return 0
left = root.left
right = root.right
leftdepth = 0
rightdepth = 0
while left:
left = left.left
leftdepth += 1
while right:
right = right.right
rightdepth += 1
if leftdepth == rightdepth:
return (2<<leftdepth)-1
return self.countNodes(root.left)+self.countNodes(root.right)+1
